Submission #1195538

#TimeUsernameProblemLanguageResultExecution timeMemory
1195538tutisMessage (IOI24_message)C++20
95 / 100
506 ms864 KiB
#include "message.h" #include <algorithm> #include <chrono> #include <iostream> #include <random> #include <bitset> #include <vector> #include <deque> #include <assert.h> #include <math.h> using namespace std; int counter = 0; bitset<31> masks[200]; const int64_t seed1 = 5; int tests = 10000; bitset<31> globC; bool initialized = false; mt19937_64 rngSending(0); bitset<31> send(bitset<31> A, bitset<31> C) { if (counter >= 199) { assert(false); } A = A ^ masks[counter]; vector<bool> Avector(31); for (int i = 0; i < 31; i++) { Avector[i] = A[i]; if (C[i]) { Avector[i] = rngSending() % 2; } } vector<bool> recVector = send_packet(Avector); bitset<31> received; for (int j = 0; j < 31; j++) { received[j] = recVector[j]; } received = received ^ masks[counter]; counter++; return received; } const int Q = 67; deque<bool> prepareBits(vector<bool> M, bitset<31> C) { deque<bool> X; mt19937_64 rng(C.to_ullong()); for (int i = 0; i < 16 * Q - 27 - 1025; i++) { X.push_back(rng() % 2 == 1); } int offset = 1024 - M.size(); for (int i = 0; i < offset; i++) { X.push_back(1); } X.push_back(0); for (int v : M) { X.push_back(v); } return X; } void init() { counter = 0; if (!initialized) { mt19937_64 rng(seed1); for (int i = 0; i < 200; i++) { for (int j = 0; j < 31; j++) { masks[i] = rng(); } } } initialized = true; } void send_message(vector<bool> M, vector<bool> Cvect) { init(); bitset<31> C; for (int i = 0; i < 31; i++) { C[i] = Cvect[i]; } globC = C; deque<bool> X = prepareBits(M, C); int col = C.to_ullong() % 16; vector<bitset<31>> V(Q); int c1 = -1; int c = 0; for (int j = 0; j < 31; j++) { if (!C[j]) { if (c == col) { c1 = j; } c++; } } for (int i = 0; i < Q; i++) { int c = 0; for (int j = 0; j < 31; j++) { if (j == c1 && i < 27) { c1 = j; V[i][j] = C[i + 4]; } else if (!C[j]) { V[i][j] = X.front(); X.pop_front(); } if (!C[i]) { c++; } } } for (bitset<31> v : V) { send(v, C); } } std::vector<bool> receive_message(vector<vector<bool>> Rvect) { init(); vector<bitset<31>> R(Rvect.size()); for (int i = 0; i < int(Rvect.size()); i++) { bitset<31> b; for (int j = 0; j < 31; j++) { b[j] = Rvect[i][j]; } R[i] = b; } for (int i = 0; i < int(R.size()); i++) { R[i] = R[i] ^ masks[i]; } if (R.size() != Q) { assert(false); } for (int col = 0; col < 16; col++) { for (int c1 = 0; c1 < 31; c1++) { bitset<31> C(col); for (int i = 0; i < 27; i++) { C[4 + i] = R[i][c1]; } if (C.count() != 15) { continue; } if (C[c1]) { continue; } int pos = 0; for (int i = 0; i < c1; i++) { if (!C[i]) { pos++; } } if (pos != col) { continue; } deque<bool> X; for (int i = 0; i < Q; i++) { int c = 0; for (int j = 0; j < 31; j++) { if (j == c1 && i < 27) { } else if (!C[j]) { X.push_back(R[i][j]); } if (!C[i]) { c++; } } } mt19937_64 rng(C.to_ullong()); bool ok = true; for (int i = 0; i < 16 * Q - 27 - 1025; i++) { bool v = rng() % 2 == 1; bool w = X.front(); X.pop_front(); if (v != w) { ok = false; } } if (!ok) { continue; } int offset = 0; while (offset < int(X.size()) && X[offset]) { offset++; } vector<bool> answer; for (int i = offset + 1; i < int(X.size()); i++) { answer.push_back(X[i]); } while (answer.size() < 1025) { answer.push_back(0); } while ((1024 - int(answer.size())) != offset && answer.size() > 0) { answer.pop_back(); } return answer; } } assert(false); return {}; } // vector<vector<bool>> sent; // int main() // { // mt19937_64 rng(5); // int maxQ = 0; // double avg = 0; // for (int i = 0; i < tests; i++) // { // vector<bool> msg(1024); // for (int i = 0; i < int(msg.size()); i++) // { // msg[i] = rng() % 2; // } // vector<bool> Cvect{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; // shuffle(Cvect.begin(), Cvect.end(), rng); // send_message(msg, // Cvect); // vector<bool> received = receive_message(sent); // maxQ = max(maxQ, int(sent.size())); // avg += sent.size(); // if (msg != received) // { // cout << "maxQ: " << maxQ << " i: " << i << endl; // cout << "mismatch!" << endl; // for (int i : msg) // { // cout << i; // } // cout << endl; // for (int i : received) // { // cout << i; // } // cout << endl; // exit(0); // } // else // { // } // sent = {}; // } // cout << maxQ << " " << avg / tests << endl; // } // vector<bool> send_packet(std::vector<bool> A) // { // sent.push_back(A); // return A; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...