oj.uz

Submission #47523

# Submission time Handle Problem Language Result Execution time Memory
47523 2018-05-04T19:17:04 Z sampriti Parrots (IOI11_parrots) C++17
100 / 100
 10 ms 3040 KB 
#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];
			}
		}
	}
}


#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1008 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1904 KB Output is correct
2 Correct 4 ms 1944 KB Output is correct
3 Correct 5 ms 2344 KB Output is correct
4 Correct 5 ms 2456 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2528 KB Output is correct
2 Correct 5 ms 2576 KB Output is correct
3 Correct 5 ms 2576 KB Output is correct
4 Correct 5 ms 2592 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2600 KB Output is correct
2 Correct 5 ms 2600 KB Output is correct
3 Correct 5 ms 2616 KB Output is correct
4 Correct 7 ms 2624 KB Output is correct
5 Correct 7 ms 2640 KB Output is correct
6 Correct 7 ms 2656 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2672 KB Output is correct - P = 5.000000
2 Correct 7 ms 2680 KB Output is correct - P = 5.000000
3 Correct 7 ms 2696 KB Output is correct - P = 4.939394
4 Correct 9 ms 2712 KB Output is correct - P = 4.920000
5 Correct 10 ms 2736 KB Output is correct - P = 5.000000
6 Correct 10 ms 2992 KB Output is correct - P = 4.952381
7 Correct 10 ms 3040 KB Output is correct - P = 5.000000