Submission #1194567

#TimeUsernameProblemLanguageResultExecution timeMemory
1194567aykhn메시지 (IOI24_message)C++20
72.85 / 100
439 ms884 KiB
#include "message.h" #include <bits/stdc++.h> using namespace std; const int B = 1, REV = 1; const int SEED = 18681; mt19937 rng; int o[(1 << 5)][31]; // int o[31] = {9, 17, 7, 27, 10, 22, 21, 6, 30, 3, 24, 15, 29, 19, 2, 13, 23, 20, 14, 1, 25, 5, 4, 8, 0, 16, 18, 28, 11, 12, 26}; int calc(vector<bool> C, int k) { int res = 0; vector<int> unlock; for (int i = 0; i < 31 && unlock.size() < 16;) { if (31 - i == 16 - (int)unlock.size()) { for (int j = i; j < 31; j++) unlock.push_back(o[k][j]); break; } vector<bool> v(31, 0); int j = 0; while (i < 31 && j < unlock.size()) { if (C[o[k][i]] == 0) v[unlock[j]] = 1, unlock.push_back(o[k][i]); else v[unlock[j]] = 0; i++, j++; } if ((31 - i) < (16 - (int)unlock.size()) * 2) { for (int l = i; l < 31; l++) v[o[k][l]] = (C[o[k][i]] == 0); if (C[o[k][i]] == 0) unlock.push_back(o[k][i]); i++; } res++; } return res; } void send_message(vector<bool> M, vector<bool> C) { rng = mt19937(SEED); for (int i = 0; i < (1 << B); i++) { for (int j = 0; j < 31; j++) { o[i][j] = rng() % (j + 1); for (int k = 0; k < j; k++) { if (o[i][k] >= o[i][j]) o[i][k]++; } } } if (REV) { for (int i = 0; i < (1 << B); i++) { for (int j = 0; j < 31; j++) { o[i + (1 << B)][j] = o[i][j]; } reverse(o[i + (1 << B)], o[i + (1 << B)] + 31); } } int n = M.size(); int cost[(1 << (B + REV))]; for (int i = 0; i < (1 << (B + REV)); i++) cost[i] = calc(C, i); int k = min_element(cost, cost + (1 << (B + REV))) - cost; for (int i = 0; i < B + REV; i++) send_packet(vector<bool>(31, k >> i & 1)); vector<int> unlock; for (int i = 0; i < 31 && unlock.size() < 16;) { if (31 - i == 16 - (int)unlock.size()) { for (int j = i; j < 31; j++) unlock.push_back(o[k][j]); break; } vector<bool> v(31, 0); int j = 0; while (i < 31 && j < unlock.size()) { if (C[o[k][i]] == 0) v[unlock[j]] = 1, unlock.push_back(o[k][i]); else v[unlock[j]] = 0; i++, j++; } if ((31 - i) < (16 - (int)unlock.size()) * 2) { for (int l = i; l < 31; l++) v[o[k][l]] = (C[o[k][i]] == 0); if (C[o[k][i]] == 0) unlock.push_back(o[k][i]); i++; } send_packet(v); } { vector<bool> v(31, 0); for (int i = 0; i <= 10; i++) v[unlock[i]] = (n >> i & 1); send_packet(v); } for (int i = 0; i < (n + 15) / 16; i++) { vector<bool> v(31, 0); for (int j = 0; j < 16; j++) { if (i * 16 + j >= n) break; v[unlock[j]] = M[i * 16 + j]; } send_packet(v); } } vector<bool> receive_message(vector<vector<bool>> R) { rng = mt19937(SEED); for (int i = 0; i < (1 << B); i++) { for (int j = 0; j < 31; j++) { o[i][j] = rng() % (j + 1); for (int k = 0; k < j; k++) { if (o[i][k] >= o[i][j]) o[i][k]++; } } } if (REV) { for (int i = 0; i < (1 << B); i++) { for (int j = 0; j < 31; j++) { o[i + (1 << B)][j] = o[i][j]; } reverse(o[i + (1 << B)], o[i + (1 << B)] + 31); } } vector<int> unlock; int cur = -1; auto nxt = [&]() { return R[++cur]; }; auto get = [&](vector<bool> A) { int cnt = 0; for (auto i : A) cnt += (int)i; return cnt >= 16; }; int k = 0; for (int i = 0; i < (B + REV); i++) k |= (get(nxt()) << i); for (int i = 0; i < 31 && unlock.size() < 16;) { if (31 - i == 16 - (int)unlock.size()) { for (int j = i; j < 31; j++) unlock.push_back(o[k][j]); break; } vector<bool> v = nxt(); int j = 0; while (i < 31 && j < unlock.size()) { if (v[unlock[j]] == 1) unlock.push_back(o[k][i]); i++, j++; } vector<int> un(31, 0); for (int j : unlock) un[j] = 1; if ((31 - i) < (16 - (int)unlock.size()) * 2) { int cnt = 0; for (int l = i; l < 31; l++) cnt += (int)v[o[k][l]]; if (cnt >= (16 - (int)unlock.size())) unlock.push_back(o[k][i]); i++; } } vector<bool> sz = nxt(); int n = 0; for (int i = 0; i <= 10; i++) { if (sz[unlock[i]]) n |= (1 << i); } vector<bool> res(n, 0); for (int i = 0; i < (n + 15) / 16; i++) { vector<bool> v = nxt(); for (int j = 0; j < 16; j++) { if (i * 16 + j >= n) break; res[i * 16 + j] = v[unlock[j]]; } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...