Submission #105388

#	Time	Username	Problem	Language	Result	Execution time	Memory
105388		eriksuenderhauf	Parrots (IOI11_parrots)	C++11	100 / 100	504 ms	232952 KiB

encoder

#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
//#include "grader.h"
using namespace std;

struct bigInt
{
	const int sz = 80;
	int val[81];

	bigInt() {
		memset(val, 0, sizeof val);
	}

	bigInt &operator += (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] += rhs.val[i];
			val[i + 1] += (val[i] >> 8);
			val[i] &= 255;
		}
		return *this;
	}

	bigInt &operator -= (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] -= rhs.val[i];
			if (val[i] < 0) {
				val[i + 1]--;
				val[i] += 256;
			}
		}
		return *this;
	}

	bool operator <= (const bigInt &rhs) {
		for (int i = sz - 1; i > -1; i--) {
			if (val[i] < rhs.val[i]) return 1;
			if (val[i] > rhs.val[i]) return 0;
		}
		return 1;
	}
};

static bigInt operator +(const bigInt lhs, const bigInt rhs) {
	bigInt ret;
	ret += lhs;
	ret += rhs;
	return ret;
}

static int a[800], cnt[300];
static bigInt dp[600][600];
static bool init = 1;

void encode(int n, int M[]) {
	if (init) {
		dp[0][0].val[0] = 1;
		for (int i = 1; i < 600; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i)
					dp[i][j].val[0] = 1;
				else
					dp[i][j] += dp[i - 1][j] + dp[i - 1][j - 1];
			}
		}
		init = 0;
	}
	memset(cnt, 0, sizeof cnt);
	bigInt cur;
	for (int i = 0; i < n; i++)
		cur.val[i] = M[i];
	int len = 5 * n;
	for (int i = 0; i < 256; i++) {
		while (dp[255 - i + len][len] <= cur) {
			cur -= dp[255 - i + len][len];
			len--;
			cnt[i]++;
		}
	}
	for (int j = 0; j < 256; j++)
		while (cnt[j]--)
			send(j);
}

decoder

#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
//#include "grader.h"
static int a[800], b[800];
static int val[16] = {0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0};

struct bigInt
{
	const int sz = 80;
	int val[81];

	bigInt() {
		memset(val, 0, sizeof val);
	}

	bigInt &operator += (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] += rhs.val[i];
			val[i + 1] += (val[i] >> 8);
			val[i] &= 255;
		}
		return *this;
	}

	bigInt &operator -= (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] -= rhs.val[i];
			if (val[i] < 0) {
				val[i + 1]--;
				val[i] += 256;
			}
		}
		return *this;
	}

	bool operator <= (const bigInt &rhs) {
		for (int i = sz - 1; i > -1; i--) {
			if (val[i] < rhs.val[i]) return 1;
			if (val[i] > rhs.val[i]) return 0;
		}
		return 1;
	}
};

static bigInt operator +(const bigInt lhs, const bigInt rhs) {
	bigInt ret;
	ret += lhs;
	ret += rhs;
	return ret;
}

static bigInt dp[600][600];
static bool init = 1;

void decode(int n, int L, int X[]) {
	if (init) {
		dp[0][0].val[0] = 1;
		for (int i = 1; i < 600; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i)
					dp[i][j].val[0] = 1;
				else
					dp[i][j] += dp[i - 1][j] + dp[i - 1][j - 1];
			}
		}
		init = 0;
	}
	bigInt cur;
	std::sort(X, X + L);
	int len = 5 * n - L;
	for (int i = L - 1; i > -1; i--) {
		int j = i;
		while (j > -1 && X[j] == X[i]) {
			len++; j--;
			cur += dp[255 - X[i] + len][len];
		}
		i = j + 1;
	}
	for (int i = 0; i < n; i++)
		output(cur.val[i]);
}

Compilation message (stderr)

encoder.cpp:52:12: warning: 'a' defined but not used [-Wunused-variable]
 static int a[800], cnt[300];
            ^

decoder.cpp:6:12: warning: 'val' defined but not used [-Wunused-variable]
 static int val[16] = {0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0};
            ^~~
decoder.cpp:5:20: warning: 'b' defined but not used [-Wunused-variable]
 static int a[800], b[800];
                    ^
decoder.cpp:5:12: warning: 'a' defined but not used [-Wunused-variable]
 static int a[800], b[800];
            ^

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