Submission #1220512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220512		nikulid	Message (IOI24_message)	C++20	29.32 / 100	544 ms	828 KiB

message

// 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;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 19.3175 / 90