oj.uz

Submission #1101133

# Submission time Handle Problem Language Result Execution time Memory
1101133 2024-10-15T15:22:15 Z rainboy Message (IOI24_message) C++17
100 / 100
 1188 ms 1072 KB 
/* 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 / 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 1132 ms 828 KB Used 66 days
2 Correct 1139 ms 804 KB Used 66 days
3 Correct 1179 ms 1064 KB Used 66 days
4 Correct 1188 ms 836 KB Used 66 days
5 Correct 840 ms 1064 KB Used 66 days
6 Correct 589 ms 832 KB Used 66 days
7 Correct 675 ms 832 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 1132 ms 828 KB Used 66 days
3 Correct 1139 ms 804 KB Used 66 days
4 Correct 1179 ms 1064 KB Used 66 days
5 Correct 1188 ms 836 KB Used 66 days
6 Correct 840 ms 1064 KB Used 66 days
7 Correct 589 ms 832 KB Used 66 days
8 Correct 675 ms 832 KB Used 66 days
9 Correct 1055 ms 836 KB Used 66 days
10 Correct 1048 ms 848 KB Used 66 days
11 Correct 1050 ms 808 KB Used 66 days
12 Correct 1042 ms 1000 KB Used 66 days
13 Correct 1095 ms 832 KB Used 66 days
14 Correct 811 ms 828 KB Used 66 days
15 Correct 632 ms 1072 KB Used 66 days
16 Correct 839 ms 808 KB Used 66 days
17 Correct 805 ms 916 KB Used 66 days
18 Correct 1139 ms 840 KB Used 66 days
19 Correct 1169 ms 832 KB Used 66 days
20 Correct 1187 ms 832 KB Used 66 days
21 Correct 1185 ms 816 KB Used 66 days
22 Correct 1140 ms 844 KB Used 66 days
23 Correct 1149 ms 984 KB Used 66 days
24 Correct 1135 ms 844 KB Used 66 days
25 Correct 1178 ms 1072 KB Used 66 days
26 Correct 1142 ms 1068 KB Used 66 days
27 Correct 1164 ms 820 KB Used 66 days
28 Correct 1153 ms 840 KB Used 66 days