Submission #1256268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256268		allin27x	Message (IOI24_message)	C++20	100 / 100	491 ms	852 KiB

message

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



vector<bool> send_packet(vector<bool> A);

void send_message(vector<bool> M, vector<bool> C) {
	vector<int> ps; for (int i=0; i<31; i++) if (!C[i]) ps.push_back(i);
	ps.push_back(ps[0]);
	vector<int> A(31,0);
	for (int i=0; i+1<ps.size(); i++) {
		A[ps[i]] = ps[i+1] - ps[i] - 1;
	}
	for (int i=0; i<31; i++){A[i]%=31; A[i] += 31; A[i]%=31;}
	
	vector<vector<bool>> pgs(66, vector<bool> (31, false));
	int nf = 0, ns = 0; int idx = 0; bool spam = !M.back();
	while (C[ns]) ns++;
	while (ns < 31){
		if (nf < A[ns]){
			pgs[nf][ns] = 0;
		} else if (nf == A[ns]){
			pgs[nf][ns] = 1;
		} else if (idx < M.size()){
			pgs[nf][ns] = M[idx++];
		} else {
			pgs[nf][ns] = spam;
		}
		nf++; 
		if (nf == 66) nf = 0, ns++;
		while (ns< 31 && C[ns]) ns++;
	}
	for (auto v: pgs) send_packet(v);
}

vector<bool> receive_message(vector<vector<bool>> R) {
	vector<int> to(31,0); iota(to.begin(), to.end(), 1);
	for (int i=0; i<31; i++){
		for (int j=0; j<31; j++){
			if (R[j][i]) {to[i] += j; break; }
		}
	}
	
	vector<int> good(31, 0);
	for (int i=0; i<31; i++) to[i] %= 31;
	for (int c=0; c<31; c++) {
		vector<int> vis(31, 0);
		vector<int> ds(31, 0);
		vis[c] = 1;
		for (int t_=0; t_<33; t_++) {
			for (int i=0; i<31; i++) {
				if (vis[i] && !vis[to[i]]) {
					vis[to[i]] = 1; ds[to[i]] = ds[i] + 1;
				}
			}
		}
		int g =0 ;
		for (int i=0; i<31; i++) if (to[i] == c && ds[i] == 15) g=1;
		good[c] = g;
	}
	for (int i=0; i<31; i++) if (to[i]< i) to[i] += 31;
	vector<bool> M;
	int nf = 0, ns = 0; 
	while (!good[ns]) ns++;
	while (ns < 31){
		if (nf > to[ns] - ns - 1) M.push_back(R[nf][ns]);
		nf++; 
		if (nf == 66) nf = 0, ns++;
		while (ns<31 && !good[ns]) ns++;
	}
	bool spam = M.back();
	while (spam == M.back()) M.pop_back();
	return M;
}

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