Submission #1101133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101133		rainboy	Message (IOI24_message)	C++17	100 / 100	1188 ms	1072 KiB

message

/* upsolved after discussion with scott_wu */
#include "message.h"
#include <cstring>

using namespace std;

typedef vector<bool> vb;
typedef vector<vb> vvb;

namespace encoder {
	const int N = 1024, K = 66, L = 31;
	void encode(vb bb, vb cc) {
		int n = bb.size();
		bb.resize(N + 1, 0), bb[n] = 1;
		vvb aaa(K, vb(L, 0));
		for (int u = 0, i = 0; u < L; u++)
			if (!cc[u]) {
				int d = 1;
				while (cc[(u + d) % L])
					d++;
				aaa[d - 1][u] = 1;
				for (int g = d; g < K; g++)
					aaa[g][u] = bb[i++];
			}
		for (int g = 0; g < K; g++)
			send_packet(aaa[g]);
	}
}

void send_message(vb bb, vb cc) {
	encoder::encode(bb, cc);
}

namespace decoder {
	const int N = 1024, K = 66, L = 31;
	int pp[L]; char visited[L];
	vb decode(vvb aaa) {
		for (int u = 0; u < L; u++) {
			int d = 1;
			while (d <= K && aaa[d - 1][u] == 0)
				d++;
			pp[u] = (u + d) % L;
		}
		memset(visited, 0, L * sizeof *visited);
		int w = -1;
		for (int u = 0; u < L; u++) {
			int v = u;
			while (!visited[v])
				visited[v] = -1, v = pp[v];
			if (visited[v] == -1) {
				int c = 0;
				while (visited[v] == -1)
					visited[v] = -2, v = pp[v], c++;
				if (c == 16) {
					w = v;
					while (w < pp[w])
						w = pp[w];
					w = pp[w];
					break;
				}
			}
			v = u;
			while (visited[v] != 1)
				visited[v] = 1, v = pp[v];
		}
		vb bb(N + 1, 0);
		int u = w, i = 0;
		do {
			int d = 1;
			while (d <= K && aaa[d - 1][u] == 0)
				d++;
			int g = d;
			while (g < K)
				bb[i++] = aaa[g++][u];
		} while ((u = pp[u]) != w);
		int n = N;
		while (bb[n] == 0)
			n--;
		bb.resize(n);
		return bb;
	}
}

vb receive_message(vvb aaa) {
	return decoder::decode(aaa);
}

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