Submission #1248110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248110		lukav	Message (IOI24_message)	C++20	0 / 100	112 ms	852 KiB

message

#include <bits/stdc++.h>
//#include <message.h>
using namespace std;
#define ll long long
#define vec vector

string to_string(vec<bool> numbers) {
	string text = "{";
	for (auto i = numbers.begin(); i != numbers.end(); i++) {
		if (*i) {text += '1';}
		else {text += '0';}
		if (next(i) != numbers.end()) {text += ", ";}
	} text += '}';
	return text;
}
string to_string(vec<vec<bool>> numbers) {
	string text = "{";
	int indexo = 0;
	for (auto i = numbers.begin(); i != numbers.end(); i++) {
		text += to_string(indexo) + ": " + to_string(*i);
		indexo++;
		if (next(i) != numbers.end()) {text += "\n";}
	} text += '}';
	return text;
}
vec<bool> receive_message(vec<vec<bool>> R) {
	int leftbound = 0, rightbound = 30;
	int i = 0;
	while (leftbound < rightbound) {
		int temp = (leftbound + rightbound) / 2;
		vec<bool> packet = R[i];
		int numofzeros = 0, numofones = 0;
		for (int j = 0; j < 31; j++) {
			if (packet[j] == 1) {numofones++;}
			else {numofzeros++;}
		}
		if (numofzeros >= 16) {rightbound = temp;}
		else {leftbound = temp + 1;}
		//cout << numofzeros << " " << numofones << endl;
		i++;
	} int index = leftbound;
	
	vec<bool> C(31, 1);
	bool is_break = false;
	if (index != 30) {
		int icopy = i;
		int indexofC = 0;
		C[index] = 0;
		C[index + 1] = 0;
		while (!is_break) {
			if (indexofC == index) {indexofC += 2;}
			if (indexofC < 31) {
				C[indexofC] = R[icopy][index];
				indexofC++;
			} if (indexofC < 31) {
				C[indexofC] = R[icopy][index + 1];
				indexofC++;
			} if (icopy == 19) {is_break = true;}
			icopy++;
		} icopy--;
		
	} else {
		C = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
	}

	vec<bool> lastpacket = R[R.size() - 1];
	vec<bool> binary;
	for (int j = 0; j < 31; j++) {
		if (C[j] == 0) {
			binary.push_back(lastpacket[j]);
			if (binary.size() == 11) {break;}
		}
	} int poweroftwo = 1024;
	int n = 0;
	for (int i = 0; i < 11; i++) {
		n += binary[i] * poweroftwo;
		poweroftwo /= 2;
	}
	
	//-------------------------------------------------------------------------
	vec<bool> M;
	is_break = false;
	for (int j = i; j < R.size() - 1; j++) {
		if (is_break) {break;}
		for (int k = 0; k < 31; k++) {
			if (C[k] == 0) {
				if (M.size() == n) {is_break = true; break;}
				if (index == 30 || j > 19) {
					// +character
					M.push_back(R[j][k]);
				} else if (j == 19) {
					if (k != index + 1) {M.push_back(R[j][k]);}
					// only if k != index + 1
				} else { // index < 30 and i <= 18
					if (k != index && k != index + 1) {
						M.push_back(R[j][k]);

					}
					// only if k != index and k != index + 1
				}
			}
		}
	}
	//---------------------------------------------------------------------------
	//cout << endl << to_string(M) << endl;
	//cout << to_string(C);
	return M;
}
vec<bool> send_packet(vec<bool> A);
void send_message(vec<bool> M, vec<bool> C) {
	int n = M.size();

	vec<vec<bool>> packets;
	int index = 30;
	for (int i = 0; i < 30; i++) {
		if (C[i] == 0 && C[i + 1] == 0) {
			index = i;
			break;
		}
	}
	int leftbound = 0, rightbound = 30;
	while (leftbound < rightbound) {
		int temp = (leftbound + rightbound) / 2;
		vec<bool> packet;
		if (index > temp) {
			leftbound = temp + 1;
			packet.resize(31, 1);
		} else {
			rightbound = temp;
			packet.resize(31, 0);
		}
		packets.push_back(packet);
	}
	//cout << to_string(packets) << endl << endl;
	bool is_break = false;
	int indexofmsg = 0, indexofC = 0;
	int indexinlastmsg;
	if (index == 30) {indexofC = 31;}
	while (!is_break) {
		vec<bool> packet(31, 0);
		for (int j = 0; j < 31; j++) {
			//cout << j << " " << indexofmsg << " " << indexofC << " " << alreadyknown << endl;
			if (indexofC == index) {indexofC += 2;}
			if ((j == index || j == index + 1) && indexofC < 31) {
				packet[j] = C[indexofC];
				indexofC++;
			} else if (C[j] == 0 && indexofmsg < n) {
				packet[j] = M[indexofmsg];
				indexofmsg++;
				if (indexofmsg == n) {indexinlastmsg = j;}
			}
		}
		if (indexofmsg == n && indexofC == 31) {is_break = true;}
		packets.push_back(packet);
	}
	
	//cout << n;
	vec<bool> lastpacket(31, 0);
	vec<bool> binary;
	int poweroftwo = 1024;
	while (poweroftwo != 0) {
		if (n >= poweroftwo) {
			n -= poweroftwo;
			binary.push_back(1);
		} else {binary.push_back(0);}
		poweroftwo /= 2;
	}
	int j = 0;
	for (int i = 0; i < 31; i++) {
		if (C[i] == 0) {
			lastpacket[i] = binary[j]; j++;
			if (j == 11) {break;}
		}
	} packets.push_back(lastpacket);
	//cout << n << endl << endl;

	//cout << to_string(packets) << endl;
	//cout << to_string(M) << endl;
	//cout << to_string(C) << endl;
	//cout << endl << to_string(M) << endl;
	for (int i = 0; i < packets.size(); i++) {
		send_packet(packets[i]);
	}
	//receive_message(packets);
}

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