Submission #1106479

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106479	2024-10-30T12:39:24 Z	Octagons	Message (IOI24_message)	C++17	100 / 100	1235 ms	1172 KB

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 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	656 KB	Used 66 days

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1186 ms	1096 KB	Used 66 days
2	Correct	1222 ms	1100 KB	Used 66 days
3	Correct	1184 ms	860 KB	Used 66 days
4	Correct	1137 ms	832 KB	Used 66 days
5	Correct	855 ms	836 KB	Used 66 days
6	Correct	659 ms	832 KB	Used 66 days
7	Correct	811 ms	860 KB	Used 66 days

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	656 KB	Used 66 days
2	Correct	1186 ms	1096 KB	Used 66 days
3	Correct	1222 ms	1100 KB	Used 66 days
4	Correct	1184 ms	860 KB	Used 66 days
5	Correct	1137 ms	832 KB	Used 66 days
6	Correct	855 ms	836 KB	Used 66 days
7	Correct	659 ms	832 KB	Used 66 days
8	Correct	811 ms	860 KB	Used 66 days
9	Correct	1175 ms	856 KB	Used 66 days
10	Correct	1203 ms	836 KB	Used 66 days
11	Correct	1233 ms	832 KB	Used 66 days
12	Correct	1193 ms	836 KB	Used 66 days
13	Correct	1186 ms	832 KB	Used 66 days
14	Correct	850 ms	856 KB	Used 66 days
15	Correct	652 ms	1088 KB	Used 66 days
16	Correct	863 ms	836 KB	Used 66 days
17	Correct	838 ms	1172 KB	Used 66 days
18	Correct	1174 ms	836 KB	Used 66 days
19	Correct	1182 ms	840 KB	Used 66 days
20	Correct	1182 ms	860 KB	Used 66 days
21	Correct	1180 ms	856 KB	Used 66 days
22	Correct	1184 ms	856 KB	Used 66 days
23	Correct	1218 ms	840 KB	Used 66 days
24	Correct	1235 ms	856 KB	Used 66 days
25	Correct	1190 ms	856 KB	Used 66 days
26	Correct	1173 ms	860 KB	Used 66 days
27	Correct	1200 ms	932 KB	Used 66 days
28	Correct	1218 ms	864 KB	Used 66 days