Submission #1244737

#TimeUsernameProblemLanguageResultExecution timeMemory
1244737allin27xMessage (IOI24_message)C++20
0 / 100
54 ms840 KiB
#include <bits/stdc++.h> using namespace std; const int SEED = 5; vector<bool> send_packet(vector<bool> A); void send_message(vector<bool> M, vector<bool> C) { mt19937 rng(SEED); vector<int> prm(31,0); iota(prm.begin(), prm.end(), 0); shuffle(prm.begin(), prm.end(), rng); vector<pair<int,int>> ps; for (int i=0; i<31; i++) if (!C[i]) ps.push_back({prm[i], i}); sort(ps.begin(), ps.end());ps.push_back(ps[0]); vector<int> A(31,0); for (int i=0; i+1<ps.size(); i++) { A[ps[i].second] = ps[i+1].first - ps[i].first - 1; } for (int i=0; i<31; i++){A[i]%=31; A[i] += 31; A[i]%=31;} for (int bt=0; bt<3; bt++) { vector<bool> pt(31,0); for (int i=0; i<31; i++) pt[i] = A[i]>>bt&1; send_packet(pt); } ps.pop_back(); sort(ps.begin(), ps.end(), [](pair<int,int> a, pair<int,int> b) {return a.second < b.second;}); int S = M.size(); vector<bool> sz(31,0); for (int bt =0; bt<16; bt++) { if ((S>>bt)&1) sz[ps[bt].second] = 1; } send_packet(sz); vector<bool> pt(31,0); for (int i=0; i<31; i++) pt[i] = 0; for (int i=0; i<S; i+=16){ for (int i=0; i<31; i++) pt[i] = 0; for (int j=i; j<i+16; j++) { pt[ps[j-i].second] = M[j]; } send_packet(pt); } } vector<bool> receive_message(vector<vector<bool>> R) { mt19937 rng(SEED); vector<int> prm(31,0); iota(prm.begin(), prm.end(), 0); shuffle(prm.begin(), prm.end(), rng); vector<int> to(31,0); iota(to.begin(), to.end(), 1); for (int bt=0; bt<3; bt++) { for (int i=0; i<31; i++) { if (R[bt][i]) to[prm[i]] += 1<<bt; to[prm[i]] %= 31; } } vector<int> good(31, 0); for (int c=0; c<31; c++) { vector<int> vis(31, 0); vector<int> ds(31, 0); vis[c] = 1; for (int t_=0; t_<33; t_++) { for (int i=0; i<31; i++) { if (vis[i] && !vis[to[i]]) { vis[to[i]] = 1; ds[to[i]] = ds[i] + 1; } } } int g =0 ; for (int i=0; i<31; i++) if (to[i] == c && ds[i] == 15) g=1; good[c] = g; } vector<int> ng(31, 0); for (int i=0; i<31; i++) ng[i] = good[prm[i]]; good = ng; vector<bool> M; int sz = 0; int bt = 0; for (int i=0; i<31; i++) { if (good[i]) sz += R[3][i] * (1<<bt), bt++; } for (int i=4; i<R.size(); i++) { for (int j=0; j<31; j++) { if (!good[j]) continue; M.push_back(R[i][j]); if (M.size() == sz) return M; } } return M; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...