#include // clang-format off using namespace std; void print0(){}; template void print0(H h,T... t){cout<void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);} #define debug1(a) { cerr<<#a<<":"<; // clang-format on namespace marathon { mt19937 engine(0); clock_t start_time; double now() { return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC; } void marathon_init() { start_time = clock(); random_device seed_gen; engine.seed(seed_gen()); } int randint(int mn, int mx) { int rng = mx - mn + 1; return mn + (engine() % rng); } bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) { const int ANNEAL_RND = 1e8; const double ANNEAL_EPS = 1e-6; double temp = (begin_temp * (end_time - cur_time) + end_temp * (cur_time - begin_time)) / (end_time - begin_time); return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS); } } // namespace marathon const int N2 = 36; const int N = 6; const int SCORE_BASE = 3; const double END_TIME = 1900; struct six { int val[6]; }; vector all_rolls; map, int> rev_all_rolls; void make_all_rolls() { for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { for (int c = 0; c < N; c++) { for (int d = 0; d < N; d++) { for (int e = 0; e < N; e++) { for (int f = 0; f < N; f++) { six s; for (int j = 0; j < N; j++) { s.val[j] = 0; } s.val[a]++; s.val[b]++; s.val[c]++; s.val[d]++; s.val[e]++; s.val[f]++; vector r(N); for (int j = 0; j < N; j++) { r[j] = s.val[j]; } rev_all_rolls[r] = all_rolls.size(); all_rolls.push_back(s); } } } } } } } int calc_score(vector> &perm, vector &rolls) { int score = 0; for (int i = 0; i < N; i++) { for (int d = 0; d < N; d++) { int cnt = 0; for (int j = 0; j < N; j++) { int rollid = perm[i][j]; int roll_cnt = all_rolls[rolls[rollid]].val[d]; if (!roll_cnt) { cnt = 0; break; } cnt += roll_cnt; } if (!cnt) continue; score += cnt - N + SCORE_BASE; } } for (int j = 0; j < N; j++) { for (int d = 0; d < N; d++) { int cnt = 0; for (int i = 0; i < N; i++) { int rollid = perm[i][j]; int roll_cnt = all_rolls[rolls[rollid]].val[d]; if (!roll_cnt) { cnt = 0; break; } cnt += roll_cnt; } if (!cnt) continue; score += cnt - N + SCORE_BASE; } } return score; } int row_score(vector> &perm, vector &rolls, int xi) { int score = 0; { for (int d = 0; d < N; d++) { int cnt = 0; for (int j = 0; j < N; j++) { int rollid = perm[xi][j]; int roll_cnt = rolls[rollid].val[d]; if (!roll_cnt) { cnt = 0; break; } cnt += roll_cnt; } if (!cnt) continue; score += cnt - N + SCORE_BASE; } } return score; } int random_dice_roll() { return marathon::engine() % all_rolls.size(); } int monte_carlo_score(int s_turn, vector &s_rolls, vector> &s_perm, int si, int sj) { int MONTE_CARLO_ITER = 1000; if (s_turn < 10) MONTE_CARLO_ITER = 300; int score = 0; for (int iter = 0; iter < MONTE_CARLO_ITER; iter++) { auto rolls = s_rolls; auto perm = s_perm; perm[si][sj] = s_turn; vector rests; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (perm[i][j] < 0) rests.push_back({i, j}); } } shuffle(rests.begin(), rests.end(), marathon::engine); for (int turn = s_turn + 1; turn < N2; turn++) { pii pt = rests.back(); rests.pop_back(); perm[pt.first][pt.second] = turn; rolls[turn] = random_dice_roll(); } score += calc_score(perm, rolls); } return score; } pii select_op(int turn, vector &rolls, vector> &perm) { vector> scores; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (perm[i][j] >= 0) continue; int score = monte_carlo_score(turn, rolls, perm, i, j); scores.push_back({score, {i, j}}); } } sort(scores.rbegin(), scores.rend()); return scores[0].second; } int main() { marathon::marathon_init(); make_all_rolls(); vector rolls(N2); vector> perm(N, vector(N, -1)); for (int turn = 0; turn < N2 - 1; turn++) { vector s(N); for (int j = 0; j < N; j++) { int d; cin >> d; d--; s[d]++; } rolls[turn] = rev_all_rolls[s]; pii op = select_op(turn, rolls, perm); cout << op.first + 1 << " " << op.second + 1 << endl; perm[op.first][op.second] = turn; } { rolls[N2 - 1] = random_dice_roll(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (perm[i][j] < 0) { perm[i][j] = N2 - 1; } } } int score = calc_score(perm, rolls); int now = marathon::now(); debug2(score, now); } return 0; }