#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |