Submission #523976

#	Time	Username	Problem	Language	Result	Execution time	Memory
523976		sidon	Parrots (IOI11_parrots)	C++17	100 / 100	10 ms	1348 KiB

encoder

#include <bits/stdc++.h>
#include "encoderlib.h"
using namespace std;

using ll = long long;
const int LIM = 28;

void encode(int N, int M[]) {
	ll dp[36][LIM] = {};
	for(int i = 0; i < 36; ++i) {
		for(int j = 0; j < LIM; ++j) {
			if(!(i | j)) dp[i][j] = 1;
			if(i) dp[i][j] += dp[i-1][j];
			if(j) dp[i][j] += dp[i][j-1];
		}
	}

	int B = 0, len, NB;

	while(++B) {
		for(int k = len = 0; k < 60; ++k)
			if(dp[B-1][LIM-1] >= (1LL<<k)) len = k;

		NB = min((5 * N) / B, 9);

		if((8 * N) <= NB * len) break;
	}

	for(int i = 0; i < NB; ++i) {
		ll K = 0;
		for(int j = 0; j < len; ++j) {
			int pos = (i * len + j);
			bool on = pos / 8 < N ? (M[pos / 8] & (1 << (pos % 8))) : 0;
			if(on) K |= 1LL << j;
		}

		for(int j = B, cur = LIM - 1; j--; ) {
			while(dp[j][cur] <= K) K -= dp[j][cur--];
			send(i * LIM + cur);
		}
		assert(!K);
	}
}

decoder

#include <bits/stdc++.h>
#include "decoderlib.h"
using namespace std;

using ll = long long;
const int LIM = 28;

void decode(int N, int L, int X[])	{
	sort(X, X + L);
	ll dp[36][LIM] = {};

	for(int i = 0; i < 36; ++i) {
		for(int j = 0; j < LIM; ++j) {
			if(!(i | j)) dp[i][j] = 1;
			if(i) dp[i][j] += dp[i-1][j];
			if(j) dp[i][j] += dp[i][j-1];
		}
	}

	int B = 0, len, NB;

	while(++B) {
		for(int k = len = 0; k < 60; ++k)
			if(dp[B-1][LIM-1] >= (1LL<<k)) len = k;

		NB = min((5 * N) / B, 9);

		if((8 * N) <= NB * len) break;
	}

	int curBit = 0, curNum = 0;

	for(int i = 0; i < NB; ++i) {
		ll K = 0; int cur = X[i * B + B - 1] % LIM;
		for(int j = B; j--; )
			while((X[i * B + j] % LIM) < cur) K += dp[j][cur--];

		for(int j = 0; j < len; ++j) {
			if(K & (1LL << j)) curNum |= 1LL << curBit;

			if(++curBit > 7) {
				output(curNum);
				curNum = curBit = 0;
				if(!(--N)) return;
			}
		}
	}
}

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