Submission #1106479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106479		Octagons	Message (IOI24_message)	C++17	100 / 100	1235 ms	1172 KiB

message

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

void send_message(vector<bool> M, vector<bool> C) {
	bool op = (1 ^ M.back());
	while (M.size() != 1025) {
		M.push_back(op);
	}
	vector<vector<bool>> p(66, vector<bool> (31, 0));
	int cur = 0;
	for (int i = 0; i < 31; i++) {
		if (C[i])continue;
		int nxt = 0;
		while (C[(i + nxt + 1) % 31]) {
			nxt++;
		}
		p[nxt][i] = true;
		for (int j = nxt+1; j < 66; j++) {
			p[j][i] = M[cur++];
		}
	}
	for (auto &i : p) {
		send_packet(i);
	}
}

vector<bool> receive_message(vector<vector<bool>> p) {
	int nxt[31], tmp[31];
	vector<bool> ret;
	vector<int> val;
	for (int i = 0; i < 31; i++) {
		nxt[i] = 0;
		while (nxt[i] < 66 && p[nxt[i]][i] == 0)nxt[i]++;
		tmp[i] = nxt[i];
		nxt[i] = (i + nxt[i] + 1) % 31;
	}
	for (int i = 0; i < 31; i++) {
		vector<bool> vis(31, false);
		int cnt = 0;
		int cur = i;
		while (!vis[cur]) {
			cnt++;
			vis[cur] = true;
			cur = nxt[cur];
		}
		if (cnt >= 16) {
			for (int j = 0; j < 16; j++) {
				val.push_back(cur);
				cur = nxt[cur];
			}
			break;
		}
	}
	sort(val.begin(), val.end());
	for (auto &i : val) {
		nxt[i] = tmp[i];
		for (int j = nxt[i]+1; j < 66 && ret.size() < 1025; j++) {
			ret.push_back(p[j][i]);
		}
	}
	bool op = ret.back();
	while (ret.back() == op)ret.pop_back();
	return ret;
}

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