Submission #1253966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253966		PanosPask	메시지 (IOI24_message)	C++20	100 / 100	381 ms	824 KiB

message

#include "message.h"
#include <stack>
#define pb push_back
#define CHECK_BIT(var, pos) (((var) & (1 << (pos))) != 0)

using namespace std;

const int N = 31;
const int GOOD = 16;

vector<bool> visited(N, false);
vector<bool> on_stack(N, false);
stack<int> s;

void dfs(int node, vector<bool>& C, vector<int>& dest) {
	if (visited[node]) {
		if (!on_stack[node]) {
			return;
		}
		// Found cycle, time to count length
		int len = 1;
		vector<int> cycle;
		cycle.pb(node);
		while (s.top() != node) {
			cycle.pb(s.top());
			s.pop();
			len++;
		}

		if (cycle.size() == GOOD) {
			// Found it!
			for (auto u : cycle) {
				C[u] = false;
			}
		}

		return;
	}

	visited[node] = on_stack[node] = true;
	s.push(node);
	dfs(dest[node], C, dest);
	on_stack[node] = false;

	if (!s.empty()) {
		s.pop();
	}
}

void send_message(vector<bool> M, vector<bool> C) {
	// Augment the message
	M.pb(1);

	// Find the good positions
	vector<int> positions;
	for (int i = 0; i < N; i++) {
		if (!C[i]) {
			positions.pb(i);
		}
	}
	positions.pb(positions[0] + N);

	int idx = 0;
	for (int p = 1; p <= 32 || idx < M.size(); p++) {
		vector<bool> packet(N, false);

		for (int i = 0; i < GOOD; i++) {
			int a = positions[i];
			int b = positions[i + 1];

			if (b - a > p) {
				packet[a] = 0;
			}
			else if (b - a == p) {
				packet[a] = 1;
			}
			else {
				// Send message info
				if (idx < M.size()) {
					packet[a] = M[idx];
					idx++;
				}
				else {
					packet[a] = 0;
				}
			}
		}

		send_packet(packet);
	}
}

vector<bool> receive_message(vector<vector<bool>> R) {
	vector<bool> C(N, true);

	vector<int> dest(N);
	// Retrieve destination of each position
	for (int i = 0; i < N; i++) {
		int p = 0;
		while (p < R.size() && R[p][i] == 0) {
			p++;
		}

		dest[i] = (i + p + 1) % N;
	}

	// Find cycle of length GOOD
	visited.assign(N, false);
	on_stack.assign(N, false);
	for (int i = 0; i < N; i++) {
		if (!visited[i]) {
			dfs(i, C, dest);
		}
	}

	// Retrieve message
	vector<bool> message;
	vector<bool> done(N, false);
	for (int p = 0; p < R.size(); p++) {
		for (int i = 0; i < N; i++) {
			if (C[i]) {
				continue;
			}
			else if (!done[i]) {
				done[i] = R[p][i];
			}
			else {
				message.pb(R[p][i]);
			}
		}
	}

	while (message.back() == 0) {
		message.pop_back();
	}
	message.pop_back();

	return message;
}

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