Submission #58674

#	Time	Username	Problem	Language	Result	Execution time	Memory
58674		kingpig9	Parrots (IOI11_parrots)	C++11	100 / 100	816 ms	23712 KiB

encoder

//START COPY

#include <bits/stdc++.h>
#include "encoderlib.h"

using namespace std;
typedef long long ll;
#define fillchar(a, s) memset((a), (s), sizeof(a))

struct bigint1 {
	unsigned arr[18];

	bigint1() {
		fillchar(arr, 0);
	}

	bigint1 (int x) {
		fillchar(arr, 0);
		arr[0] = x;
	}
};

static void operator += (bigint1 &b1, bigint1 b2) {
	bool carry = 0;
	for (int i = 0; i < 18; i++) {
		ll x = ll(b1.arr[i]) + b2.arr[i] + carry;
		b1.arr[i] = x;
		carry = (x >= (1ll << 32));
	}
}

static void operator -= (bigint1 &b1, bigint1 b2) {
	//b1 + (~b2) + 1
	//optimize the +1
	for (int i = 0; i < 18; i++) {
		b2.arr[i] = ~b2.arr[i];
	}
	b1 += b2;
	b1 += bigint1(1);
}

static bigint1 operator + (bigint1 b1, bigint1 b2) {
	b1 += b2;
	return b1;
}

static bigint1 operator - (bigint1 b1, bigint1 b2) {
	b1 -= b2;
	return b1;
}

static bool operator < (bigint1 b1, bigint1 b2) {
	for (int i = 17; i >= 0; i--) {
		if (b1.arr[i] < b2.arr[i]) {
			return true;
		}
		if (b1.arr[i] > b2.arr[i]) {
			return false;
		}
	}
	return false;
}

static bool operator >= (bigint1 b1, bigint1 b2) {
	return !(b1 < b2);
}

static bool operator > (bigint1 b1, bigint1 b2) {
	return b2 < b1;
}

static bool operator <= (bigint1 b1, bigint1 b2) {
	return !(b2 < b1);
}

static const int MAXV = 5 * 64 + 256;
static bigint1 cho[MAXV][256];
static void precomp() {
	for (int i = 0; i < MAXV; i++) {
		cho[i][0].arr[0] = 1;
		for (int j = 1; j <= i && j < 256; j++) {
			cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
		}
	}
}

static bigint1 nsum (int n, int s) {
	return cho[n + s - 1][n - 1];
}

static int N;
static int K;

//END COPY

void encode (int nn, int mm[]) {
	N = nn;
	K = 5 * N;
	precomp();

	//ok let's go!
	bigint1 rnk = bigint1();
	for (int i = 0; i < N; i++) {
		rnk.arr[i / 4] |= (mm[i] << (8 * (i % 4)));
	}

	//ok now get this number rank
	vector<int> ans;
	for (int i = 0; i < K; i++) {
		//if you put this one then what will you get?
		int prv = (ans.empty() ? 0 : ans.back());
		for (int j = prv; j < 256; j++) {
			//test if next one is > j.
			//if not then choose this one and break
			bigint1 nways = nsum(256 - j, K - 1 - i);
			if (rnk >= nways) {
				rnk -= nways;
			} else {
				ans.push_back(j);
				break;
			}
		}
	}

	//printf("SEND:");
	for (int x : ans) {
		//printf(" %d", x);
		send(x);
	}
	//printf("\n");
}

decoder

//START COPY

#include <bits/stdc++.h>
#include "decoderlib.h"

using namespace std;
typedef long long ll;
#define fillchar(a, s) memset((a), (s), sizeof(a))

struct bigint2 {
	unsigned arr[18];

	bigint2() {
		fillchar(arr, 0);
	}

	bigint2 (int x) {
		fillchar(arr, 0);
		arr[0] = x;
	}
};

static void operator += (bigint2 &b1, bigint2 b2) {
	bool carry = 0;
	for (int i = 0; i < 18; i++) {
		ll x = ll(b1.arr[i]) + b2.arr[i] + carry;
		b1.arr[i] = x;
		carry = (x >= (1ll << 32));
	}
}

static void operator -= (bigint2 &b1, bigint2 b2) {
	//b1 + (~b2) + 1
	//optimize the +1
	for (int i = 0; i < 18; i++) {
		b2.arr[i] = ~b2.arr[i];
	}
	b1 += b2;
	b1 += bigint2(1);
}

static bigint2 operator + (bigint2 b1, bigint2 b2) {
	b1 += b2;
	return b1;
}

static bigint2 operator - (bigint2 b1, bigint2 b2) {
	b1 -= b2;
	return b1;
}

static bool operator < (bigint2 b1, bigint2 b2) {
	for (int i = 17; i >= 0; i--) {
		if (b1.arr[i] < b2.arr[i]) {
			return true;
		}
		if (b1.arr[i] > b2.arr[i]) {
			return false;
		}
	}
	return false;
}

static bool operator >= (bigint2 b1, bigint2 b2) {
	return !(b1 < b2);
}

static bool operator > (bigint2 b1, bigint2 b2) {
	return b2 < b1;
}

static bool operator <= (bigint2 b1, bigint2 b2) {
	return !(b2 < b1);
}

static const int MAXV = 5 * 64 + 256;
static bigint2 cho[MAXV][256];
static void precomp() {
	for (int i = 0; i < MAXV; i++) {
		cho[i][0].arr[0] = 1;
		for (int j = 1; j <= i && j < 256; j++) {
			cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
		}
	}
}

static bigint2 nsum (int n, int s) {
	return cho[n + s - 1][n - 1];
}

static int N;
static int K;

//END COPY


void decode (int nn, int kk, int X[]) {
	N = nn;
	K = kk;
	precomp();
	sort(X, X + K);
	//find the rank of this one
	bigint2 rnk = bigint2();
	for (int i = 0; i < K; i++) {
		int prv = (i == 0 ? 0 : X[i - 1]);
		for (int j = prv; j < X[i]; j++) {
			//add this amount of stuff
			bigint2 nways = nsum(256 - j, K - 1 - i);
			rnk += nways;
		}
	}

	//printf("OUTPUT:");
	for (int i = 0; i < N; i++) {
		//ok let's do this
		int val = (rnk.arr[i / 4] >> (8 * (i % 4))) & 255;
		//printf(" %d", val);
		output(val);
	}
	//printf("\n");
}

Compilation message (stderr)

encoder.cpp:72:13: warning: 'bool operator<=(bigint1, bigint1)' defined but not used [-Wunused-function]
 static bool operator <= (bigint1 b1, bigint1 b2) {
             ^~~~~~~~
encoder.cpp:68:13: warning: 'bool operator>(bigint1, bigint1)' defined but not used [-Wunused-function]
 static bool operator > (bigint1 b1, bigint1 b2) {
             ^~~~~~~~
encoder.cpp:47:16: warning: 'bigint1 operator-(bigint1, bigint1)' defined but not used [-Wunused-function]
 static bigint1 operator - (bigint1 b1, bigint1 b2) {
                ^~~~~~~~

decoder.cpp:72:13: warning: 'bool operator<=(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bool operator <= (bigint2 b1, bigint2 b2) {
             ^~~~~~~~
decoder.cpp:68:13: warning: 'bool operator>(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bool operator > (bigint2 b1, bigint2 b2) {
             ^~~~~~~~
decoder.cpp:64:13: warning: 'bool operator>=(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bool operator >= (bigint2 b1, bigint2 b2) {
             ^~~~~~~~
decoder.cpp:47:16: warning: 'bigint2 operator-(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bigint2 operator - (bigint2 b1, bigint2 b2) {
                ^~~~~~~~

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