Submission #62179

#	Time	Username	Problem	Language	Result	Execution time	Memory
62179		aome	Parrots (IOI11_parrots)	C++17	98 / 100	153 ms	2936 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#include <bits/stdc++.h>

using namespace std;

static const int K = 10;

static int A[K * K * K * K], B[320];

void encode(int N, int M[]) {
	vector< pair<int, int> > vec;
	for (int i = 0; i < K * K * K * K; ++i) {
		int val = i;
		int cnt = 0;
		for (int j = 0; j < 4; ++j) {
			cnt += val % K, val /= K;
		}
		vec.push_back({cnt, i});
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < 320; ++i) A[vec[i].second] = i, B[i] = vec[i].second;
	for (int i = 0; i < N; ++i) {
		int P = -1;
		for (int j = 0; j < i; ++j) {
			if (M[j] == M[i]) { P = j; break; }
		}
		int val = M[i];
		if (P != -1) val = 256 + P;
		val = B[val];
		for (int j = 0; j < 4; ++j) {
			int tmp = val % K; val /= K;
			while (tmp--) send(i * 4 + j);
		}
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"

#include <bits/stdc++.h>

using namespace std;

static const int K = 10;

static int res[64];
static int cnt[256];
static int A[K * K * K * K], B[320];

void decode(int N, int L, int X[]) {
	vector< pair<int, int> > vec;
	for (int i = 0; i < K * K * K * K; ++i) {
		int val = i;
		int cnt = 0;
		for (int j = 0; j < 4; ++j) {
			cnt += val % K, val /= K;
		}
		vec.push_back({cnt, i});
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < 320; ++i) A[vec[i].second] = i, B[i] = vec[i].second;
	memset(cnt, 0, sizeof cnt);
	for (int i = 0; i < L; ++i) cnt[X[i]]++;
	for (int i = 0; i < N; ++i) {
		int val = 0;
		for (int j = 3; j >= 0; --j) {
			val = val * K + cnt[i * 4 + j];
		}
		val = A[val];
		if (val < 256) res[i] = val;
		else res[i] = res[val - 256];
		output(res[i]);
	}
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 17 / 19