Submission #403014

#	Time	Username	Problem	Language	Result	Execution time	Memory
403014		rainboy	Parrots (IOI11_parrots)	C11	17 / 100	2369 ms	42688 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <string.h>

#define N	64
#define A	256
#define K	(N * 5)

int dp[A + 1][K + 1][N];

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

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

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

	for (i = 0; i < N; i++)
		aa[i] -= bb[i];
	for (i = 0; i < N; i++)
		if (aa[i] < 0)
			aa[i] += A, 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, N * sizeof *dp[a][k]), dp[a][k][0] = 1;
			else
				add(dp[a - 1][k], dp[a][k - 1], dp[a][k]);
}

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

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

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

	memset(aa, 0, N * sizeof *aa), memcpy(aa, aa_, n * sizeof *aa_);
	init();
	a = A, k = K;
	while (a > 0 || k > 0) {
		int i;

		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--;
		}
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <string.h>

#define N	64
#define A	256
#define K	(N * 5)

int dp_[A + 1][K + 1][N];

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

	for (i = 0; i < N; i++)
		cc[i] = aa[i] + bb[i];
	for (i = 0; i < N; i++)
		if (cc[i] >= A) {
			if (i + 1 == N)
				cc[i] = A;
			else
				cc[i] -= A, 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)
				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 int aa[N], 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, N * 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]);
}

Compilation message (stderr)

encoder.c: In function 'encode':
encoder.c:63:7: warning: unused variable 'i' [-Wunused-variable]
   63 |   int i;
      |       ^

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

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