Submission #47523

#	Time	Username	Problem	Language	Result	Execution time	Memory
47523		sampriti	Parrots (IOI11_parrots)	C++17	100 / 100	10 ms	3040 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;

// dp[i][j] = number of non-decreasing subsequences of length i with prev element j

const int K = 16;

void encode(int N, int M[]) {
	long long dp[21][K];
	for(int j = 0; j < K; j++) dp[0][j] = 1;
	for(int i = 1; i <= 20; i++) {
		for(int j = 0; j < K; j++) {
			dp[i][j] = 0;
			for(int k = j; k < K; k++) dp[i][j] += dp[i - 1][k];
		}
	}
	long long sum[21];
	sum[0] = 0;
	for(int i = 1; i <= 20; i++) sum[i] = sum[i - 1] + dp[i][0];

	vector<int> A;
	for(int i = 0; i < N; i++) A.push_back(M[i]);

	if(N % 4 != 0) {
		for(int i = 0; i < (4 - (N % 4)); i++) A.push_back(0);
		N += 4 - (N % 4);
	}

	for(int i = 0; i < N; i += 4) {
		int grp_num = i/4;

		long long num = 0;
		for(int j = 0; j < 4; j++) {
			num |= ((long long)A[i+j]) << (j*8);
		}

		int len_req = -1;
		for(int j = 1; j <= 20; j++) {
			if(num < sum[j]) {
				len_req = j;
				break;
			}
		}
		assert(len_req != -1);
		num -= sum[len_req - 1];

		vector<int> ans;
		int prv = 0;
		for(int j = len_req; j > 0; j--) {
			long long sum = 0;
			for(int k = prv; k < K; k++) {
				if(num < (sum + dp[j - 1][k])) {
					send((grp_num << 4) | k);
					num -= sum;
					prv = k;
					break;
				}
				sum += dp[j - 1][k];
			}
		}
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;

// dp[i][j] = number of non-decreasing subsequences of length i with prev element j

const int K = 16;

void decode(int N, int L, int X[]) {
	long long dp[21][K];
	for(int j = 0; j < K; j++) dp[0][j] = 1;
	for(int i = 1; i <= 20; i++) {
		for(int j = 0; j < K; j++) {
			dp[i][j] = 0;
			for(int k = j; k < K; k++) dp[i][j] += dp[i - 1][k];
		}
	}
	long long sum[21];
	sum[0] = 0;
	for(int i = 1; i <= 20; i++) sum[i] = sum[i - 1] + dp[i][0];

	int N_ = N;
	if(N % 4 != 0) N += 4 - (N % 4);

	for(int grp_num = 0; grp_num < N/4; grp_num++) {
		vector<int> perm;
		for(int i = 0; i < L; i++) {
			if((X[i] >> 4) == grp_num) {
				perm.push_back(X[i] % (1 << 4));
			}
		}
		sort(perm.begin(), perm.end());
		int len_req = perm.size();

		long long num = 0;
		int prv = 0;
		for(int i = len_req; i > 0; i--) {
			for(int j = prv; j < perm[len_req - i]; j++) {
				num += dp[i - 1][j];
			}
			prv = perm[len_req - i];
		}
		num += sum[len_req - 1];

		for(int i = 0; i < 4; i++) {
			if(grp_num * 4 + i < N_) {
				output((num >> (i*8)) % (1 << 8));
			}
		}
	}
};

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