Submission #1201852

#TimeUsernameProblemLanguageResultExecution timeMemory
1201852Bzslayed메시지 (IOI24_message)C++20
100 / 100
440 ms868 KiB
#include <bits/stdc++.h> #include "message.h" using namespace std; int nxt[31]; bool vis[31]; int cycle = 1, endp = -1; void cycle_dfs(int x){ vis[x] = true; if (!vis[nxt[x]]){ cycle++; cycle_dfs(nxt[x]); } else{ endp = nxt[x]; return; } } void send_message(vector<bool> M, vector<bool> C){ vector<bool> tempC; for (auto it : C) tempC.push_back(it); for (auto it : C){ tempC.push_back(it); if (it == 0) break; } int dist[31]; int prev = -1; for (int i=0; i<(int)tempC.size(); i++){ if (tempC[i] == 0){ if (prev != -1) dist[prev] = i-prev; prev = i; } } for (int i=0; i<31; i++){ if (C[i] == 1) dist[i] = 0; } // for (int i=0; i<31; i++) cout << dist[i] << " "; // cout << "\n"; int msg_len = M.size(); vector<bool> pad_message; while (pad_message.size()+1+msg_len < 1025) pad_message.push_back(0); pad_message.push_back(1); for (auto it : M) pad_message.push_back(it); // for (auto it : pad_message) cout << it; // cout << "\n"; vector<vector<bool>> packets(66, vector<bool>(31)); vector<vector<bool>> occupied(66, vector<bool>(31)); for (int i=0; i<31; i++){ if (dist[i] == 0) continue; for (int j=0; j<dist[i]-1; j++){ packets[j][i] = 0; occupied[j][i] = 1; } packets[dist[i]-1][i] = 1; occupied[dist[i]-1][i] = 1; } int ptr = 0; for (int i=0; i<66; i++){ for (int j=0; j<31; j++){ if (!occupied[i][j] && C[j] == 0){ if (ptr > 1024) break; packets[i][j] = pad_message[ptr]; ptr++; } } send_packet(packets[i]); } // cout << "testing" << "\n"; // for (int i=0; i<66; i++){ // for (int j=0; j<31; j++){ // cout << packets[i][j] << " "; // } // cout << "\n"; // } } vector<bool> receive_message(vector<vector<bool>> R){ int dist_bits[31]; for (int i=0; i<31; i++){ for (int j=0; j<16; j++){ if (R[j][i] == 1){ nxt[i] = (i+j+1)%31; dist_bits[i] = j+1; break; } } } unordered_map<int, bool> not_cont; for (int i=0; i<31; i++){ cycle = 1, endp = -1; memset(vis, false, sizeof(vis)); cycle_dfs(i); if (endp != i) continue; if (cycle == 16){ memset(vis, false, sizeof(vis)); int cur = i; not_cont[cur] = true; for (int j=0; j<15; j++){ cur = nxt[cur]; not_cont[cur] = true; } break; } } for (int i=0; i<31; i++){ if (!not_cont[i]) dist_bits[i] = 0; } vector<bool> ans; for (int i=0; i<66; i++){ for (int j=0; j<31; j++){ if (!not_cont[j]) continue; if (dist_bits[j] == 0) ans.push_back(R[i][j]); else dist_bits[j]--; } } // cout << ans.size() << "\n"; // for (auto it : ans) cout << it; assert(ans.size() == 1025); reverse(ans.begin(), ans.end()); bool seen = false; while (!seen){ bool lst = ans.back(); ans.pop_back(); if (lst == 1) seen = true; } reverse(ans.begin(), ans.end()); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...