Submission #1123750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123750		math_rabbit_1028	Message (IOI24_message)	C++20	43.96 / 100	778 ms	832 KiB

message

#include "message.h"
using namespace std;

vector<bool> add_blank(vector<bool> A, vector<bool> C) {
	vector<bool> ret;
	reverse(A.begin(), A.end());
	for (int i = 0; i < 31; i++) {
		if (C[i]) ret.push_back(0);
		else {
			ret.push_back(A.back());
			A.pop_back();
		}
	}
	return ret;
}

void send_message(vector<bool> M, vector<bool> C) {
	int S = (int)(M.size());
	vector<bool> T(31, 1), F(31, 0);
	for (int i = 0; i < 16; i++) {
		if (C[i]) send_packet(T);
		else send_packet(F);
	}
	vector<int> idx;
	for (int i = 0; ; i++) {
		if (!C[i]) idx.push_back(i);
		if (idx.size() == 5) break;
	}
	if (C[16]) {
		vector<bool> T(31, 1);
		T[idx[0]] = C[17];
		send_packet(T);
	}
	else {
		vector<bool> F(31, 0);
		F[idx[0]] = C[17];
		send_packet(F);
	}
	if (C[18]) {
		vector<bool> T(31, 1);
		T[idx[0]] = C[19];
		T[idx[1]] = C[20];
		send_packet(T);
	}
	else {
		vector<bool> F(31, 0);
		F[idx[0]] = C[19];
		F[idx[1]] = C[20];
		send_packet(F);
	}
	if (C[21]) {
		vector<bool> T(31, 1);
		T[idx[0]] = C[22];
		T[idx[1]] = C[23];
		T[idx[2]] = C[24];
		T[idx[3]] = C[25];
		T[idx[4]] = C[26];
		send_packet(T);
	}
	else {
		vector<bool> F(31, 0);
		F[idx[0]] = C[22];
		F[idx[1]] = C[23];
		F[idx[2]] = C[24];
		F[idx[3]] = C[25];
		F[idx[4]] = C[26];
		send_packet(F);
	}
	if (C[27]) {
		vector<bool> T(31, 1);
		T[idx[0]] = C[28];
		T[idx[1]] = C[29];
		send_packet(T);
	}
	else {
		vector<bool> F(31, 0);
		F[idx[0]] = C[28];
		F[idx[1]] = C[29];
		send_packet(F);
	}

	for (int i = 0; i < S; i += 16) {
		vector<bool> A(16, 0);
		for (int j = 0; j < 16; j++) {
			A[j] = (i+j < S) ? M[i+j] : 0;
		}
		send_packet(add_blank(A, C));
	}
	
	vector<bool> A(16, 0);
	for (int j = 0; j < 16; j++) {
		if (j < (S+15)%16+1) A[j] = 1;
		else A[j] = 0;
	}
	send_packet(add_blank(A, C));
}

vector<bool> rem_blank(vector<bool> A, vector<bool> C) {
	vector<bool> ret;
	for (int i = 0; i < 31; i++) {
		if (C[i]) continue;
		else {
			ret.push_back(A[i]);
		}
	}
	return ret;
}

vector<bool> receive_message(vector<vector<bool>> R) {
	vector<bool> C(31, 0);
  	for (int i = 0; i < 16; i++) {
		vector<bool> V = R[i];
		int a = 0, b = 0; // 0 - 1
		for (int i = 0; i < 31; i++) {
			if (V[i]) b++;
			else a++;
		}
		if (a > b) C[i] = 0;
		else C[i] = 1;
	}

	vector<int> idx, non, ch(31, 0);
	for (int i = 0; i < 16; i++) {
		if (!C[i]) idx.push_back(i);
		if (idx.size() == 1) break;
	}
	for (int i = 0; i < 16; i++) {
		if (C[i]) non.push_back(i);
		if (non.size() == 1) break;
	}
	if (non.size() == 0) non.push_back(16);
	vector<bool> V = R[16];
	ch[idx[0]] = 1;
	C[17] = V[idx[0]];
	ch[non[0]] = 1;
	int a = 0, b = 0; // 0 - 1
	for (int i = 0; i < 31; i++) {
		if (ch[i]) continue;
		if (V[i]) b++;
		else a++;
	}
	if (a > b) C[16] = 0;
	else C[16] = 1;
	idx.clear(); non.clear(); ch = vector<int>(31, 0);
	for (int i = 0; i < 18; i++) {
		if (!C[i]) idx.push_back(i);
		if (idx.size() == 2) break;
	}
	for (int i = 0; i < 18; i++) {
		if (C[i]) non.push_back(i);
		if (non.size() == 2) break;
	}
	V = R[17];
	ch[idx[0]] = 1;
	ch[idx[1]] = 1;
	C[19] = V[idx[0]];
	C[20] = V[idx[1]];
	ch[non[0]] = 1;
	ch[non[1]] = 1;
	a = 0, b = 0; // 0 - 1
	for (int i = 0; i < 31; i++) {
		if (ch[i]) continue;
		if (V[i]) b++;
		else a++;
	}
	if (a > b) C[18] = 0;
	else C[18] = 1;
	idx.clear(); non.clear(); ch = vector<int>(31, 0);
	for (int i = 0; i < 21; i++) {
		if (!C[i]) idx.push_back(i);
		if (idx.size() == 5) break;
	}
	for (int i = 0; i < 21; i++) {
		if (C[i]) non.push_back(i);
		if (non.size() == 5) break;
	}
	V = R[18];
	ch[idx[0]] = 1;
	ch[idx[1]] = 1;
	ch[idx[2]] = 1;
	ch[idx[3]] = 1;
	ch[idx[4]] = 1;
	C[22] = V[idx[0]];
	C[23] = V[idx[1]];
	C[24] = V[idx[2]];
	C[25] = V[idx[3]];
	C[26] = V[idx[4]];
	ch[non[0]] = 1;
	ch[non[1]] = 1;
	ch[non[2]] = 1;
	ch[non[3]] = 1;
	ch[non[4]] = 1;
	a = 0, b = 0; // 0 - 1
	for (int i = 0; i < 31; i++) {
		if (ch[i]) continue;
		if (V[i]) b++;
		else a++;
	}
	if (a > b) C[21] = 0;
	else C[21] = 1;
	idx.clear(); non.clear(); ch = vector<int>(31, 0);
	for (int i = 0; i < 27; i++) {
		if (!C[i]) idx.push_back(i);
		if (idx.size() == 2) break;
	}
	for (int i = 0; i < 27; i++) {
		if (C[i]) non.push_back(i);
		if (non.size() == 2) break;
	}
	V = R[19];
	ch[idx[0]] = 1;
	ch[idx[1]] = 1;
	C[28] = V[idx[0]];
	C[29] = V[idx[1]];
	ch[non[0]] = 1;
	ch[non[1]] = 1;
	a = 0, b = 0; // 0 - 1
	for (int i = 0; i < 31; i++) {
		if (ch[i]) continue;
		if (V[i]) b++;
		else a++;
	}
	if (a > b) C[27] = 0;
	else C[27] = 1;
	idx.clear(); non.clear(); ch = vector<int>(31, 0);

	a = 0, b = 0; // 0 - 1
	for (int i = 0; i < 30; i++) {
		if (C[i]) b++;
		else a++;
	}
	if (a < 16) C[30] = 0;
	else C[30] = 1;

	vector<bool> ret;
	for (int i = 20; i < R.size()-1; i++) {
		vector<bool> V = rem_blank(R[i], C);
		for (int j = 0; j < 16; j++) ret.push_back(V[j]);
	}
	V = rem_blank(R.back(), C);
	for (int i = 0; i < 16; i++) {
		if (!V[i]) ret.pop_back();
	}
	return ret;
}

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