Submission #1258621

#TimeUsernameProblemLanguageResultExecution timeMemory
1258621nerrrminMessage (IOI24_message)C++20
51.70 / 100
448 ms868 KiB
#include "message.h" #define pb push_back #include<bits/stdc++.h> using namespace std; bool known[40]; void send_message(std::vector<bool> M, std::vector<bool> C) { for (int i = 0; i < C.size(); ++ i) C[i] = 1- C[i]; for (int i = 0; i < 31; ++ i) known[i] = 0; int first = 0; for (int i = 0; i < 31; ++ i) { if(C[i] == 1) { first = i; break; } } for (int i = 0; i < first; ++ i) known[i] = 0; known[first] = 1; vector < bool > ones, zeroes; for (int i = 0; i < 31; ++ i) ones.pb(1); for (int i = 0; i < 31; ++ i) zeroes.pb(0); for (int bit = 0; bit < 5; ++ bit) { if((1 << bit) & first) { send_packet(ones); } else send_packet(zeroes); } int some = 1, j = first; for (int i = first+1; i < 31; ++ i) { vector < bool > ans; int to_be_discovered = j+1; if(to_be_discovered >= 31)break; vector < int > newfound; for (int pos = 0; pos < 31; ++ pos) { if(!known[pos])ans.pb(0); else { if(to_be_discovered < 31) { ans.pb(C[to_be_discovered]); if(C[to_be_discovered] == 1)known[to_be_discovered] = 1;//newfound.pb(to_be_discovered); } else ans.pb(0); to_be_discovered ++; j ++; } } // for (auto x: newfound) // known[x] = 1; send_packet(ans); } vector < int > ours; for (int i = 0; i < 31; ++ i) if(known[i])ours.pb(i); int sz = M.size(); int step = 0; vector < bool > szpacket; for (int i = 0; i < 31; ++ i) { if(known[i] == 1) { if(sz & (1 << step))szpacket.pb(1); else szpacket.pb(0); step ++; } else szpacket.pb(0); } send_packet(szpacket); int i = 0; int s = M.size(); while(i < s) { vector < bool > packet; for (int j = 0; j < 31; ++ j) packet.pb(0); for (auto x: ours) { if(i >= s)break; packet[x] = M[i]; i ++; } send_packet(packet); } } int val[40]; std::vector<bool> receive_message(std::vector<std::vector<bool>> R) { int found = 0, pos = 0; for (int i = 0; i < 31; ++ i) val[i] = -1; int curr = 5; int first = 0; for (int i = 0; i < 5; ++ i) { int cnt0 = 0, cnt1 = 0; for (auto x: R[i]) { if(x)cnt1 ++; else cnt0 ++; } if(cnt1 > cnt0)first += (1 << i); } for (int i = 0; i < first; ++ i) val[i] = 0; val[first] = 1; pos = first + 1; found = 1; while(pos < 31) { if(!found) { int cnt0 = 0, cnt1 = 0; for (auto x: R[curr]) { if(x)cnt1 ++; else cnt0 ++; } if(cnt0 >= cnt1)val[pos] = 0; else val[pos] = 1; if(val[pos] == 1)found = 1; pos ++; } else { vector < pair < int, int > > mp; for (int i = 0; i < 31; ++ i) { if(val[i] == 1) { int x = R[curr][i]; val[pos] = x; // mp.pb(make_pair(pos, x)); pos ++; } } // for (auto &[pp, vv]: mp) // { // / val[pp] = vv; // } } curr ++; } int sz = 0, id = 0, step = 1; for (auto x: R[curr]) { if(val[id] == 1) { if(x)sz += step; step *= 2; } id ++; } curr ++; int s = sz; vector < bool > ans; int mark = 0; while(curr < R.size()) { for (int i = 0; i < 31; ++ i) { if(val[i] == 1) ans.pb(R[curr][i]); } curr ++; } while(ans.size() > s) ans.pop_back(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...