Submission #1233563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233563		AMnu	Message (IOI24_message)	C++20	100 / 100	382 ms	848 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;

int A[31], cnt;
vector <int> v;

void send_message(vector<bool> M, vector<bool> C) {
	M.push_back(1);
	while (M.size() < 1025) {
		M.push_back(0);
	}
	v.clear();
	for (int i=0;i<31;i++) {
		if (C[i]) {
			A[i] = 67;
		}
		else {
			v.push_back(i);
		}
	}
	v.push_back(v[0]+31);
	for (int i=0;i<16;i++) {
		A[v[i]] = v[i+1]-v[i];
	}
	cnt = 0;
	vector<bool> B(31, 0);
	for (int i=1;i<=66;i++) {
		for (int j=0;j<31;j++) {
			if (i == A[j]) {
				B[j] = 1;
			}
			if (i > A[j]) {
				B[j] = M[cnt];
				cnt++;
			}
		}
		send_packet(B);
	}
}

vector<bool> receive_message(vector<vector<bool> > R) {
	vector<bool> ans;
	for (int i=0;i<31;i++) {
		A[i] = 31;
		for (int j=0;j<30;j++) {
			if (R[j][i]) {
				A[i] = j+1;
				break;
			}
		}
	}
	for (int i=0;i<31;i++) {
		if (!A[i]) continue;
		v.clear();
		int j=i, tmp;
		while (A[j]) {
			v.push_back(j);
			tmp = A[j];
			A[j] = 0;
			j=(j+tmp)%31;
		}
		if (v.size() < 16) continue;
		reverse(v.begin(),v.end());
		while (v.size() > 16) {
			v.pop_back();
		}
		sort(v.begin(),v.end());
		break;
	}
	v.push_back(v[0]+31);
	for (int i=0;i<16;i++) {
		A[v[i]] = v[i+1]-v[i];
	}
	v.pop_back();
	for (int i=0;i<66;i++) {
		for (int j : v) {
			if (i >= A[j]) {
				ans.push_back(R[i][j]);
			}
		}
	}
	while (!ans.back()) {
		ans.pop_back();
	}
	ans.pop_back();
	return ans;
}

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