// Nico
// IOI 2024 DAY 1 QUESTION 2
// message
#include "message.h"
// #include <iostream>
using namespace std;
#define pb push_back
/*
-- NOTES ---
> S itself can be compressed into 4 bits
- this can be done with binary, where the 4 bits are a number (-1 < x < 16)
- this number will represent the number of unused bits in the final sent packet
*/
void send_message(vector<bool> M, vector<bool> C) {
vector<bool> A(31, 0);
// send 31 packets so the receiver can identify the corrupted bits..
for(int i=0; i<31; i++){
A = vector<bool>(31, C[i]);
send_packet(A); // SEND
}
// .
// send S in binary
int S = M.size();
int cnt=0;
for(int i=1024; i>0; i /= 2){ // note that i is not the index (bad practice sry)
while(C[cnt])cnt++; // skip corrupted bits
if(S>=i){
S -= i;
A[cnt]=1;
} else{
A[cnt]=0;
}
cnt++;
}
while(cnt<31){
A[cnt]=0;
cnt++;
}
send_packet(A); // SEND
S=M.size();
// .
// send message in non-corrupt bits
int cor;
for(int i=0; i<S; i+=16){
cnt=0;
for(int c=0; c<31; c++){
while(C[c] == 1)c++; // skips corrupt bits (let them just be 0 by default)
A[c] = M[i+cnt];
cnt++;
}
send_packet(A); // SEND
}
// .
return;
}
vector<bool> receive_message(vector<vector<bool>> R) {
vector<bool> B(31),C(31);
// first 31 packets are to find the corrupt bits..
int sum;
for(int i=0; i<31; i++){
B = R[i];
sum=0;
for(bool d:B)sum+=d;
if(sum<16){
// more 0s than 1s
C[i] = 0;
} else{
// more 1s than 0s
C[i] = 1;
}
}
// .
// next 1 packet is to find S..
B = R[31];
/* {1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1} */
int S = 0;
int w=1024;
for(int i=0; i<31; i++){
while(C[i])i++;
if(B[i]) S += w;
w/=2;
}
// .
// rest of the packets are the message..
vector<bool> M;
for(int i=32; i<R.size(); i++){
B = R[i];
for(int j=0; j<31; j++){ // goes through each bit in the packet
if(C[j]==0 && M.size()<S){
M.pb(B[j]);
}
}
}
// .
return M;
}
