제출 #1253966

#제출 시각아이디문제언어결과실행 시간메모리
1253966PanosPask메시지 (IOI24_message)C++20
100 / 100
381 ms824 KiB
#include "message.h" #include <stack> #define pb push_back #define CHECK_BIT(var, pos) (((var) & (1 << (pos))) != 0) using namespace std; const int N = 31; const int GOOD = 16; vector<bool> visited(N, false); vector<bool> on_stack(N, false); stack<int> s; void dfs(int node, vector<bool>& C, vector<int>& dest) { if (visited[node]) { if (!on_stack[node]) { return; } // Found cycle, time to count length int len = 1; vector<int> cycle; cycle.pb(node); while (s.top() != node) { cycle.pb(s.top()); s.pop(); len++; } if (cycle.size() == GOOD) { // Found it! for (auto u : cycle) { C[u] = false; } } return; } visited[node] = on_stack[node] = true; s.push(node); dfs(dest[node], C, dest); on_stack[node] = false; if (!s.empty()) { s.pop(); } } void send_message(vector<bool> M, vector<bool> C) { // Augment the message M.pb(1); // Find the good positions vector<int> positions; for (int i = 0; i < N; i++) { if (!C[i]) { positions.pb(i); } } positions.pb(positions[0] + N); int idx = 0; for (int p = 1; p <= 32 || idx < M.size(); p++) { vector<bool> packet(N, false); for (int i = 0; i < GOOD; i++) { int a = positions[i]; int b = positions[i + 1]; if (b - a > p) { packet[a] = 0; } else if (b - a == p) { packet[a] = 1; } else { // Send message info if (idx < M.size()) { packet[a] = M[idx]; idx++; } else { packet[a] = 0; } } } send_packet(packet); } } vector<bool> receive_message(vector<vector<bool>> R) { vector<bool> C(N, true); vector<int> dest(N); // Retrieve destination of each position for (int i = 0; i < N; i++) { int p = 0; while (p < R.size() && R[p][i] == 0) { p++; } dest[i] = (i + p + 1) % N; } // Find cycle of length GOOD visited.assign(N, false); on_stack.assign(N, false); for (int i = 0; i < N; i++) { if (!visited[i]) { dfs(i, C, dest); } } // Retrieve message vector<bool> message; vector<bool> done(N, false); for (int p = 0; p < R.size(); p++) { for (int i = 0; i < N; i++) { if (C[i]) { continue; } else if (!done[i]) { done[i] = R[p][i]; } else { message.pb(R[p][i]); } } } while (message.back() == 0) { message.pop_back(); } message.pop_back(); return message; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...