oj.uz

답안 #523976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523976 2022-02-08T13:46:36 Z sidon 앵무새 (IOI11_parrots) C++17
100 / 100
 10 ms 1348 KB 
#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);
	}
}
#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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1016 KB Output is correct
2 Correct 2 ms 1020 KB Output is correct
3 Correct 2 ms 984 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 2 ms 1020 KB Output is correct
3 Correct 2 ms 1012 KB Output is correct
4 Correct 2 ms 984 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1008 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 3 ms 1040 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 3 ms 1048 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 984 KB Output is correct - P = 3.375000
2 Correct 3 ms 1032 KB Output is correct - P = 3.375000
3 Correct 3 ms 1044 KB Output is correct - P = 3.272727
4 Correct 5 ms 1196 KB Output is correct - P = 4.140000
5 Correct 7 ms 1340 KB Output is correct - P = 4.800000
6 Correct 10 ms 1336 KB Output is correct - P = 4.857143
7 Correct 7 ms 1348 KB Output is correct - P = 4.921875