Submission #1253811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253811		PanosPask	Message (IOI24_message)	C++20	10 / 100	362 ms	820 KiB

message

#include "message.h"
#define pb push_back
#define CHECK_BIT(var, pos) (((var) & (1 << (pos))) != 0)

using namespace std;

const int N = 31;
const int GOOD = 16;

void majority(int b) {
	vector<bool> packet(N);
	for (int i = 0; i < N; i++) {
		packet[i] = b;
	}

	send_packet(packet);
}

int count(vector<bool> packet) {
	int one = 0;
	for (int i = 0; i < N; i++) {
		one += packet[i];
	}
	return one >= GOOD;
}

void send_message(vector<bool> M, vector<bool> C) {
	M.pb(1);
	
	// Find first good position
	int first = 0;
	while (C[first]) {
		first++;
	}
	
	for (int b = 0; b < 4; b++) {
		majority(CHECK_BIT(first, b));
	}
	
	// Bit in position first send info about freedom, other good bits send the message
	int idx = 0;
	int pos = first + 1;
	while (idx < M.size() || pos < N) {
		vector<bool> packet(N);
		int i = first;

		if (pos < N) {
			packet[first] = C[pos];
			pos++;
			i++;
		}

		while (i < N) {
			if (!C[i]) {
				if (idx < M.size()) {
					packet[i] = M[idx];
					idx++;
				}
				else {
					packet[i] = 0;
				}
			}
			i++;
		}

		send_packet(packet);
	}
}

vector<bool> receive_message(vector<vector<bool>> R) {
	int first = 0;
	int p = 0;
	for (int b = 0; b < 4; b++) {
		int res = count(R[p]);
		first += (res << b);
		p++;
	}

	vector<bool> C(N, true);
	vector<bool> message;
	int pos = first + 1;
	while (pos < N) {
		C[pos] = R[p][first];
		p++;
		pos++;
	}

	p = 4;
	pos = first + 1;
	while (p < R.size()) {
		int i = first;
		
		if (pos < N) {
			i++;
			pos++;
		}

		while (i < N) {
			if (!C[i]) {
				message.pb(R[p][i]);
			}
			i++;
		}

		p++;
	}

	while (message.back() == false) {
		message.pop_back();
	}
	message.pop_back();

	return message;
}

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