Submission #1261541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261541		software1146	Message (IOI24_message)	C++20	100 / 100	390 ms	848 KiB

message

#include "message.h"
#include <bits/stdc++.h>

using namespace std;
void send_message(std::vector<bool> M, std::vector<bool> C) {
	for (int i = 0; i < 31; ++i)
	{
		C[i] = !C[i];
	}
	int message_size = M.size();
	M.resize(1025);
	M[message_size] = true;
	int ind = 0;
	for (int i = 0; i < 31; i++){
		vector<bool> A(31);
		int j = i-1;
		if (j < 0) j = 30;
		while (C[j] == false){
			j--;
			if (j < 0) j = 30;
		}
		A[j] = C[i];
		for (int k = 0; k < 31; k++){
			if (k == j) continue;
			if (C[k]) A[k] = M[ind++];
		}
		send_packet(A);
	}
	for (int i = 31; i < 66; i++){
		vector<bool> A(31);
		for (int k = 0; k < 31; k++){
			if (C[k]) A[k] = M[ind++];
		}
		send_packet(A);
	}
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
	vector<bool> C(31,false);
	for (int x = 0; x < 31; x++){
		vector<int> trust;
		int i = x;
		trust.push_back(i);
		vector<bool> vis(31, false);
		vis[i] = true;
		for (int _ = 0; _ < 15; _++){
			for (int j = 1; j < 31; j++){
				if (vis[(trust.back()+j)%31]) continue;
				if (R[(trust.back()+j)%31][trust.back()] == 1){
					vis[(trust.back()+j)%31] = true;
					trust.push_back((trust.back()+j)%31);
					break;
				}
			}
		}
		if (trust.size() == 16 && R[trust[0]][trust.back()]){
			for (auto it : trust){
				C[it] = 1;
			}
			bool boolean=true;
			for (int i = 0; i < 31; i++){
				int j = i-1;
				if (j < 0) j = 30;
				while (C[j] == 0){
					j--;
					if (j < 0) j = 30;
					if (i == j) break;
				}
				if (i == j){
					boolean=false;
					break;
				}
				if (R[i][j] != C[i]){
					boolean=false;
					break;
				}
			}
			if (!boolean){
				for (auto it : trust){
					C[it] = 0;
				}
				continue;
			}
			break;
		}
	}
	vector<bool> ret;
	for (int i = 0; i < 31; i++){
		int j = i-1;
		if (j < 0) j = 30;
		while (C[j] == false){
			j--;
			if (j < 0) j = 30;
		}
		for (int k = 0; k < 31; k++){
			if (k == j) continue;
			if (C[k]) ret.push_back(R[i][k]);
		}
	}
	for (int i = 31; i < 66; i++){
		for (int k = 0; k < 31; k++){
			if (C[k]) ret.push_back(R[i][k]);
		}
	}
	while (ret.back() == false) ret.pop_back();
	ret.pop_back();
	return ret;
}

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