#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<<":"< 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; 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]++; 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 = 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 = 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; } six random_dice_roll() { return all_rolls[marathon::engine() % all_rolls.size()]; } int monte_carlo_score(int s_turn, vector &s_rolls, vector> &s_perm, int si, int sj) { const int MONTE_CARLO_ITER = 400; 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; for (int turn = s_turn + 1; turn < N2; turn++) { int rest = N2 - turn; int tgt = marathon::engine() % rest; int c = 0; rolls[turn] = random_dice_roll(); for (int i = 0; (c >= 0 && i < N); i++) { for (int j = 0; (c >= 0 && j < N); j++) { if (perm[i][j] >= 0) continue; if (c == tgt) { perm[i][j] = turn; c = -1; break; } c++; } } } score += calc_score(perm, rolls); } return score; } pair 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++) { six s; for (int k = 0; k < N; k++) { s.val[k] = 0; } for (int j = 0; j < N; j++) { int d; cin >> d; d--; s.val[d]++; } rolls[turn] = s; pair 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; }