oj.uz

답안 #403105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403105 2021-05-12T18:37:27 Z rainboy 앵무새 (IOI11_parrots) C
100 / 100
 671 ms 21900 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <string.h>

#define N	64
#define M	(N / 4)
#define A	256
#define B	4294967296
#define K	(N * 5)

long long dp[A + 1][K + 1][M];

void add(long long *aa, long long *bb, long long *cc) {
	int i;

	for (i = 0; i < M; i++)
		cc[i] = aa[i] + bb[i];
	for (i = 0; i < M; i++)
		if (cc[i] >= B) {
			if (i + 1 == M)
				cc[i] = B;
			else
				cc[i] -= B, cc[i + 1]++;
		}
}

void sub(long long *aa, long long *bb) {
	int i;

	for (i = 0; i < M; i++)
		aa[i] -= bb[i];
	for (i = 0; i < M; i++)
		if (aa[i] < 0)
			aa[i] += B, aa[i + 1]--;
}

void init() {
	int a, k;

	for (a = 0; a <= A; a++)
		for (k = 0; k <= K; k++)
			if (a == 0 || k == 0)
				memset(dp[a][k], 0, M * sizeof *dp[a][k]), dp[a][k][0] = 1;
			else
				add(dp[a - 1][k], dp[a][k - 1], dp[a][k]);
}

int lt(long long *aa, long long *bb) {
	int i;

	for (i = M - 1; i >= 0; i--)
		if (aa[i] != bb[i])
			return aa[i] < bb[i];
	return 0;
}

void encode(int n, int *aa_) {
	static long long aa[M];
	int i, a, k;

	init();
	memset(aa, 0, M * sizeof *aa);
	for (i = 0; i < n; i++)
		aa[i / 4] |= (long long) aa_[i] << i % 4 * 8;
	a = A, k = K;
	while (a > 0 || k > 0)
		if (k > 0 && lt(aa, dp[a][k - 1])) {
			if (a < A)
				send(a);
			k--;
		} else {
			if (k > 0)
				sub(aa, dp[a][k - 1]);
			a--;
		}
}
#include "decoder.h"
#include "decoderlib.h"
#include <string.h>

#define N	64
#define M	(N / 4)
#define A	256
#define B	4294967296
#define K	(N * 5)

long long dp_[A + 1][K + 1][M];

void add_(long long *aa, long long *bb, long long *cc) {
	int i;

	for (i = 0; i < M; i++)
		cc[i] = aa[i] + bb[i];
	for (i = 0; i < M; i++)
		if (cc[i] >= B) {
			if (i + 1 == M)
				cc[i] = B;
			else
				cc[i] -= B, cc[i + 1]++;
		}
}

void init_() {
	int a, k;

	for (a = 0; a <= A; a++)
		for (k = 0; k <= K; k++)
			if (a == 0 || k == 0)
				memset(dp_[a][k], 0, M * sizeof *dp_[a][k]), dp_[a][k][0] = 1;
			else
				add_(dp_[a - 1][k], dp_[a][k - 1], dp_[a][k]);
}

void decode(int n, int l, int *bb) {
	static long long aa[M];
	static int kk[A];
	int i, a, k;

	init_();
	memset(kk, 0, A * sizeof *kk);
	for (i = 0; i < l; i++)
		kk[bb[i]]++;
	memset(aa, 0, M * sizeof *aa);
	k = 0;
	for (a = 0; a < A; a++) {
		k += kk[a];
		if (k > 0)
			add_(aa, dp_[a + 1][k - 1], aa);
	}
	for (i = 0; i < n; i++)
		output(aa[i / 4] >> i % 4 * 8 & A - 1);
}

Compilation message

grader_decoder.c: In function 'main':
grader_decoder.c:86:2: warning: implicit declaration of function 'fcloseall'; did you mean 'fclose'? [-Wimplicit-function-declaration]
   86 |  fcloseall();
      |  ^~~~~~~~~
      |  fclose
decoder.c: In function 'decode':
decoder.c:55:33: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   55 |   output(aa[i / 4] >> i % 4 * 8 & A - 1);
      |                                 ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 626 ms 21900 KB Output is correct
2 Correct 628 ms 21656 KB Output is correct
3 Correct 663 ms 21744 KB Output is correct
4 Correct 624 ms 21724 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 630 ms 21744 KB Output is correct
2 Correct 671 ms 21652 KB Output is correct
3 Correct 651 ms 21592 KB Output is correct
4 Correct 622 ms 21664 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 618 ms 21588 KB Output is correct
2 Correct 635 ms 21792 KB Output is correct
3 Correct 623 ms 21660 KB Output is correct
4 Correct 622 ms 21720 KB Output is correct
5 Correct 634 ms 21688 KB Output is correct
6 Correct 638 ms 21560 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 625 ms 21624 KB Output is correct - P = 1.750000
2 Correct 633 ms 21648 KB Output is correct - P = 2.437500
3 Correct 663 ms 21784 KB Output is correct - P = 2.484848
4 Correct 661 ms 21676 KB Output is correct - P = 3.280000
5 Correct 627 ms 21840 KB Output is correct - P = 3.833333
6 Correct 640 ms 21732 KB Output is correct - P = 4.015873
7 Correct 649 ms 21768 KB Output is correct - P = 4.078125