Submission #1242790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242790		erray	Message (IOI24_message)	C++20	100 / 100	410 ms	948 KiB

message

#include <bits/stdc++.h>
#include "message.h"

using namespace std;

#ifdef DEBUG
	#include "debug.h"
#else 
	#define debug(...) void(37)
#endif

constexpr int N = 31, O = 16;
constexpr int Q = 66, M_len = 1025;
vector<array<int, 3>> message_positions(vector<bool> C) {
	vector<int> ones; 
	for (int i = 0; i < N; ++i) {
		if (!C[i]) {
			ones.push_back(i);
		}
	}
	assert(int(ones.size()) == O);
	vector<int> next_dist(O);
	for (int i = 0; i < O; ++i) {
		next_dist[i] = ones[(i + 1) % O] - ones[i];
	}
	next_dist[O - 1] += N;
	vector<array<int, 3>> res;
	int p = 0;
	for (int i = 0; i < O; ++i) {
		for (int j = 0; j < Q; ++j) {
			int put;
			if (j < next_dist[i] - 1) put = -2;
			else if (j == next_dist[i] - 1) put = -1;
			else put = p++;
			res.push_back({j, ones[i], put});
		}
	}
	debug(p);
	return res;
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
	M.push_back(!M.back());
	while (M.size() < M_len) M.push_back(M.back());
	vector<vector<bool>> S(Q, vector<bool>(N));
	for (auto[x, y, t] : message_positions(C)) {
		if (t == -2) S[x][y] = false;
		else if (t == -1) S[x][y] = true;
		else S[x][y] = M[t];
	}
	debug(S);
	for (int i = 0; i < Q; ++i) {
		send_packet(S[i]);
	}
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
	vector<int> point(N + 1, N);
	for (int i = 0; i < N; ++i) {
		int p = 0;
		debug(i);
		while (p < Q && !R[p][i]) ++p;
		point[i] = (i + p + 1) % N;
	}
	debug(point);
	vector<bool> C;
	for (int i = 0; i < N; ++i) {
		C.assign(N, true);
		int v = i;
		for (int j = 0; j < Q; ++j, v = point[v]) {
			if (v < N) C[v] = false;
		}
		if (accumulate(C.begin(), C.end(), 0) == O - 1) break;
	}
	debug(C);
	vector<bool> M(M_len);
	for (auto[x, y, t] : message_positions(C)) {
		if (t >= 0) {
			M[t] = R[x][y];
		}
	}
	while (M.back() == M.end()[-2]) M.pop_back();
	M.pop_back();
	return M;
}

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