Submission #1117346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117346		Nonoze	Message (IOI24_message)	C++17	100 / 100	2627 ms	1092 KiB

message

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

void send_message(vector<bool> M,  vector<bool> C) {
	int n=31;
	vector<int> nxt(n, 0);
	int prec=-1, cnt=0;
	for (int i=0; i<n; i++) {
		if (!C[i]) prec=i, cnt=0;
		cnt++;
	}
	for (int i=0; i<31; i++) {
		if (!C[i]) nxt[prec]=cnt, prec=i, cnt=0;
		cnt++;
	}
	int toadd=1024-size(M);
	vector<bool> toinsert(toadd, 0); toinsert.push_back(1);
	M.insert(M.begin(), toinsert.begin(), toinsert.end());
	int nb=66, cur=0;
	for (int t=0; t<nb; t++) {
		vector<bool> A(31, 0);
		for (int i=0; i<n; i++) if (!C[i]) {
			if (t<nxt[i]) {
				if (t<nxt[i]-1) A[i]=0;
				else A[i]=1;
			} else A[i]=M[cur++];
		}
		send_packet(A);
	}
}

vector<bool> receive_message(vector<vector<bool>> R) {
	int n=31;
	vector<int> nxt(n, 0);
	for (int i=0; i<n; i++) {
		int nb=1;
		for (int j=0; j<31; j++) {
			if (!R[j][i]) nb++;
			else break;
		}
		nxt[i]=nb;
	}
	vector<bool> works;
	for (int i=0; i<n; i++) {
		int act=i, nb=0;
		vector<bool> visited(n, 0);
		while (nb<16) {
			if (visited[act]) break;
			visited[act]=1;
			act=(act+nxt[act])%n;
			nb++;
		}
		if (nb==16 && act==i) {
			works=visited;
			break;
		}
	}
	vector<bool> M;
	for (int i=0; i<(int)R.size(); i++) {
		for (int j=0; j<n; j++) if (works[j] && i>=nxt[j]) {
			if (!M.empty() || R[i][j]) M.push_back(R[i][j]);
		}
	}
	M.erase(M.begin());
	return M;
}

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