Submission #984042

#	Time	Username	Problem	Language	Result	Execution time	Memory
984042		sleepntsheep	Parrots (IOI11_parrots)	C11	100 / 100	507 ms	22940 KiB

encoder

/* copied from rainboy orz */

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

decoder

#include "decoder.h"
#include "decoderlib.h"

#include <string.h>

#define A 256
#define K 320
#define N 64
#define M N / 4
#define B 4294967296ll

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

static void add(long long *a, long long *b, long long *c) {
    for (int i = 0; i < M; ++i)
        c[i] = a[i] + b[i];
    for (int i = 0; i < M; ++i)
        if (c[i] >= B) {
            if (i + 1 == M)
                c[i] = B;
            else
                c[i] -= B, ++c[i+1];
        }
}

static int lt(long long *a, long long *b) {
    for (int i = M - 1; i >= 0; --i)
        if (a[i] != b[i])
            return a[i] < b[i];
    return 0;
}

static void init() {
    for (int i = 0; i <= A; ++i)
        for (int j = 0; j <= K; ++j)
            if (i == 0 || j == 0)
                memset(dp[i][j], 0, sizeof **dp), dp[i][j][0] = 1;
            else
                add(dp[i-1][j], dp[i][j-1], dp[i][j]);
}



void decode(int n, int L, int X[])
{
    init();

    static int ff[A], f;
    static long long aa[M];

    f = 0;
    memset(ff, 0, sizeof ff);
    memset(aa, 0, sizeof aa);

    for (int i = 0; i < L; ++i) ++ff[X[i]];

    for (int a = 0; a < A; ++a) {
        f += ff[a];
        if (f > 0)
            add(aa, dp[a + 1][f - 1], aa);
    }

    for (int i = 0; i < n; ++i)
        output((aa[i / 4] >> (8 * (i & 3))) & 255);
}

Compilation message (stderr)

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:26:12: warning: 'lt' defined but not used [-Wunused-function]
   26 | static int lt(long long *a, long long *b) {
      |            ^~

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