제출 #1206389

#제출 시각아이디문제언어결과실행 시간메모리
1206389trimkus메시지 (IOI24_message)C++20
10 / 100
955 ms848 KiB
#include "message.h" #include <bits/stdc++.h> using namespace std; const int LIMIT = 66; void send_message(std::vector<bool> M, std::vector<bool> C) { std::vector<bool> A(31, 0); int N = (int)M.size(); vector<int> dist(31, -1); for (int i = 0; i < 31; ++i) { if (C[i] == 0) { int d = 1; for (int j = (i + 1) % 31; C[j] == 1; j = (j + 1) % 31) { d++; } dist[i] = d; } } // cout << "DIST:" << endl; // for (int i = 0; i < 31; ++i) { // cout << dist[i] << " "; // } // cout << endl; vector<bool> send[31]; int ptr = 0; for (int i = 0; i < 31; ++i) { if (C[i] == 0) { while (dist[i] > 0) { send[i].push_back(1); dist[i]--; } send[i].push_back(0); while (ptr < N && (int)send[i].size() < LIMIT) { send[i].push_back(M[ptr++]); } } while ((int)send[i].size() < LIMIT) { send[i].insert(send[i].begin(), 0); } } // for (int i = 0; i < 31; ++i) { // if (C[i] == 0 || C[i] == 1) { // cout << i << " = "; // for (auto u : send[i]) { // cout << u << " "; // } // cout << endl; // } // } // cout << "HERE!" << endl; for (int i = 0; i < 31; ++i) { // cout << i << endl; assert((int)send[i].size() == LIMIT); // cout << i << endl; } for (int i = 0; i < LIMIT; ++i) { for (int j = 0; j < 31; ++j) { A[j] = send[j][i]; } send_packet(A); } // cout << "DONE SENDING..." << endl; } std::vector<bool> receive_message(std::vector<std::vector<bool>> R) { vector<bool> res; vector<int> nxt(31, -1); vector<bool> C[31]; int N = (int)R.size(); for (int i = 0; i < N; ++i) { for (int j = 0; j < 31; ++j) { // cout << R[i][j] << " "; C[j].push_back(R[i][j]); } // cout << endl; } // cout << endl; for (int i = 0; i < 31; ++i) { auto& v = C[i]; // for (auto u : v) { // cout << u << " "; // } // cout << endl; while (v.size() && v[0] == 0) { v.erase(v.begin()); } if (!v.size()) continue; int dist = 0; while (v.size() && v[0] == 1) { dist++; v.erase(v.begin()); } // cout << i << " = " << dist << "\n"; if (v.size() == 0) continue; nxt[i] = (i + dist) % 31; v.erase(v.begin()); } int start = -1; // for (int i = 0; i < 31; ++i) { // cout << nxt[i] << " "; // } // cout << endl; for (int i = 0; start == -1 && i < 31; ++i) { if (nxt[i] == -1) continue; int j = i; int d = 0; while (d < 16 && j >= i) { d++; j = nxt[j]; if (j == i) break; } if (d == 16 && j == i) { start = i; } // cout << i << " -> " << j << endl; } assert(start != -1); bool good[31]; for (int i = 0; i < 31; ++i) good[i] = false; { int ni = start; good[ni] = true; ni = nxt[ni]; while (ni != start) { good[ni] = true; ni = nxt[ni]; } } // for (int i = 0; i < 31; ++i) { // cout << good[i] << " "; // } // cout << endl; for (int i = 0; i < 31; ++i) { if (good[i]) { auto& v = C[i]; while ((int)v.size() > 0) { res.push_back(v[0]); v.erase(v.begin()); } } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...