Submission #1276782

#TimeUsernameProblemLanguageResultExecution timeMemory
1276782avighnaMessage (IOI24_message)C++20
87.16 / 100
480 ms844 KiB
#include <bits/stdc++.h> std::vector<bool> send_packet(std::vector<bool> A); void send_message(std::vector<bool> M, std::vector<bool> C) { auto hash = [&](const std::string &data) { uint32_t hash = 2166136261; for (auto &i : data) { hash = (hash ^ i) * 16777619; } return hash; }; std::mt19937 gen(69420); std::vector<int> p(31); std::iota(p.begin(), p.end(), 0); std::shuffle(p.begin(), p.end(), gen); int bits = 0, i = 0; while (bits == 0) { bits += !C[p[i]]; i += !bits; } int channel = p[i]; std::string c_str(31, '0'); for (int i = 0; i < 31; ++i) { c_str[i] = C[i] + '0'; } std::string data, ans_str; data.reserve(66 * 31); ans_str.reserve(M.size() + 64); int cur = 0; auto push_bit = [&](bool x) { ans_str.push_back(x + '0'); while (C[cur % 31]) { data.push_back('0'), cur++; } if (cur / 31 < 31 and cur % 31 == channel) { data.push_back(c_str[cur / 31]), cur++; } while (C[cur % 31]) { data.push_back('0'), cur++; } data.push_back(x + '0'), cur++; }; auto push_num = [&](int x, int bits) { for (int i = 0; i < bits; ++i) { push_bit(x & 1 << i); } }; push_num(M.size(), 16); for (int i = 0; i < M.size(); ++i) { push_bit(M[i]); } push_num(hash(ans_str), 32); while (cur / 31 < 31) { push_bit(0); } while (cur % 31 != 0) { data.push_back('0'), cur++; } auto send_stream = [&]() { std::vector<bool> buf(31); for (int i = 0; i < data.size(); i += 31) { for (int j = 0; j < 31; ++j) { buf[j] = data[i + j] == '1'; } send_packet(buf); } }; send_stream(); } std::vector<bool> receive_message(std::vector<std::vector<bool>> R) { auto hash = [&](const std::string &data) { uint32_t hash = 2166136261; for (auto &i : data) { hash = (hash ^ i) * 16777619; } return hash; }; std::mt19937 gen(69420); std::vector<int> p(31); std::iota(p.begin(), p.end(), 0); std::shuffle(p.begin(), p.end(), gen); for (int idx = 0; idx < 31; ++idx) { int channel = p[idx]; std::vector<bool> C(31); for (int i = 0; i < 31; ++i) { C[i] = R[i][channel]; } if (C[channel]) { continue; } if (std::accumulate(C.begin(), C.end(), 0) != 15) { continue; } int cur = 0, j = 0; std::string ans_str; ans_str.reserve(66 * 31); auto recv_bit = [&](bool push) { while (C[j]) { cur += (j + 1) / 31, j = (j + 1) % 31; } if (cur < 31 and j == channel) { cur += (j + 1) / 31, j = (j + 1) % 31; } while (C[j]) { cur += (j + 1) / 31, j = (j + 1) % 31; } if (cur >= R.size()) { return 0; } int ans = R[cur][j]; cur += (j + 1) / 31, j = (j + 1) % 31; if (push) { ans_str.push_back(ans + '0'); } return ans; }; auto recv_num = [&](int bits) { int x = 0; for (int i = 0; i < bits; ++i) { x += recv_bit(bits == 16) << i; } return x; }; int size = recv_num(16); if (size > 1024) { continue; } std::vector<bool> ans(size); for (int i = 0; i < size; ++i) { ans[i] = recv_bit(true); } if (hash(ans_str) == recv_num(32)) { return ans; } } return {}; // will never happen }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...