Submission #1231540

#TimeUsernameProblemLanguageResultExecution timeMemory
1231540bangan메시지 (IOI24_message)C++20
61.19 / 100
445 ms872 KiB
#include "message.h" #include <bits/stdc++.h> using namespace std; #define pb push_back const int N = 31; void send_message(std::vector<bool> M, std::vector<bool> C) { auto work1 = [&]() -> vector<vector<bool>> { int bad=0; vector<int> ok; vector<vector<bool>> ret; for (int i=0; i<N && ok.size() != 16 && bad != 15;) { if (ok.empty()) { ret.pb(vector<bool>(N, C[i])); if (!C[i]) ok.pb(i); else bad++; i++; } else { vector<bool> pac(N, false); int j = 0; while (j < ok.size() && i+j < N) { pac[ok[j]] = C[i+j]; j++; } ret.pb(pac); for (int k=i; k < i+j; k++) { if (!C[k]) ok.pb(k); else bad++; } i+=j; } } return ret; }; auto work2 = [&]() -> vector<vector<bool>> { int bad=0; vector<int> ok; vector<vector<bool>> ret; for (int i = N-1; 0<=i && ok.size() != 16 && bad != 15;) { if (ok.empty()) { ret.pb(vector<bool>(N, C[i])); if (!C[i]) ok.pb(i); else bad++; i--; } else { vector<bool> pac(N, false); int j = 0; while (j < ok.size() && 0 <= i-j) { pac[ok[j]] = C[i-j]; j++; } ret.pb(pac); for (int k=i; i-j < k; k--) { if (!C[k]) ok.pb(k); else bad++; } i-=j; } } return ret; }; auto x = work1(); auto y = work2(); if (x.size() < y.size()) { send_packet(vector<bool>(N, false)); for (auto vec : x) send_packet(vec); } else { send_packet(vector<bool>(N, true)); for (auto vec : y) send_packet(vec); } vector<int> ok; for (int i=0; i<N; i++) if (!C[i]) ok.pb(i); auto cur = ok.begin(); vector<bool> pac(31, false); for (bool x : M) { if (cur==ok.end()) { send_packet(pac); pac = vector<bool>(31, false); cur = ok.begin(); } pac[*cur] = x; cur++; } if (cur == ok.end()) { send_packet(pac); pac = vector<bool>(31, false); cur = ok.begin(); } pac[*cur] = true; send_packet(pac); } std::vector<bool> receive_message(std::vector<std::vector<bool>> R) { reverse(R.begin(), R.end()); bool st; { int cnt[2] {}; auto vec = R.back(); R.pop_back(); for (bool x : vec) cnt[x]++; if (cnt[0]>cnt[1]) st=0; else st=1; } vector<bool> C(N); if (st==0) { vector<int> ok; int bad = 0; int i; for (i=0; i<N && ok.size() != 16 && bad != 15;) { auto vec = R.back(); R.pop_back(); if (ok.empty()) { int cnt[2] {}; for (bool x : vec) cnt[x]++; if (cnt[0]<cnt[1]) C[i]=1, bad++; else C[i]=0, ok.pb(i); i++; } else { int j = 0; while (j < ok.size() && i+j < N) { C[i+j] = vec[ok[j]]; j++; } for (int k=i; k < i+j; k++) { if (!C[k]) ok.pb(k); else bad++; } i+=j; } } for (int j=i; j<N; j++) { if (ok.size()==16) C[j] = true; else if (bad==15) C[j] = false; else assert(false); } } else { vector<int> ok; int bad = 0; int i; for (i = N-1; 0<=i && ok.size() != 16 && bad != 15;) { auto vec = R.back(); R.pop_back(); if (ok.empty()) { int cnt[2] {}; for (bool x : vec) cnt[x]++; if (cnt[0]<cnt[1]) C[i]=1, bad++; else C[i]=0, ok.pb(i); i--; } else { int j = 0; while (j < ok.size() && 0 <= i-j) { C[i-j] = vec[ok[j]]; j++; } for (int k=i; i-j < k; k--) { if (!C[k]) ok.pb(k); else bad++; } i-=j; } } for (int j=i; 0<=j; j--) { if (ok.size()==16) C[j] = true; else if (bad==15) C[j] = false; else assert(false); } } reverse(R.begin(), R.end()); int i; vector<int> ok; for (i=0; i<N; i++) if (!C[i]) ok.pb(i); vector<bool> M; for (i=0; i+1 < R.size(); i++) { auto vec = R[i]; for (int j=0; j<N; j++) if (!C[j]) M.pb(vec[j]); } auto vec = R.back(); int lst=0; for (i=0; i<N; i++) if (!C[i] && vec[i]) lst=i; for (i=0; i<lst; i++) if (!C[i]) M.pb(vec[i]); return M; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...