Submission #58670

#	Time	Username	Problem	Language	Result	Execution time	Memory
58670		kingpig9	Parrots (IOI11_parrots)	C++11	0 / 100	2083 ms	9988 KiB

encoder

//START COPY

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

using namespace std;
typedef bitset<576> bset;

static void operator += (bset &b1, bset b2) {
	bool carry = 0;
	for (int i = 0; i < 576; i++) {
		int x = int(b1[i]) + int(b2[i]) + carry;
		b1[i] = bool(x & 1);
		carry = (x >= 2);
	}
}

static void operator -= (bset &b1, bset b2) {
	//b1 + (~b2) + 1
	//optimize the +1
	for (int i = 0; i < 576; i++) {
		if (!b1[i]) {
			b1[i] = true;
			for (int j = 0; j < i; j++) {
				b1[j] = false;
			}
			break;
		}
	}
	b1 += (~b2);
}

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

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

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

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

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

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

static bset cho[576][256];
static void precomp() {
	for (int i = 0; i < 576; i++) {
		cho[i][0][0] = 1;
		for (int j = 1; j <= i && j < 256; j++) {
			cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
		}
	}
}

static bset 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!
	bset rnk = bset();
	for (int i = 0; i < N; i++) {
		rnk |= (bset(mm[i]) << (8 * i));
	}

	//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
			bset 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 bitset<576> bset;

static void operator += (bset &b1, bset b2) {
	bool carry = 0;
	for (int i = 0; i < 576; i++) {
		int x = int(b1[i]) + int(b2[i]) + carry;
		b1[i] = bool(x & 1);
		carry = (x >= 2);
	}
}

static void operator -= (bset &b1, bset b2) {
	//b1 + (~b2) + 1
	//optimize the +1
	for (int i = 0; i < 576; i++) {
		if (!b1[i]) {
			b1[i] = true;
			for (int j = 0; j < i; j++) {
				b1[j] = false;
			}
			break;
		}
	}
	b1 += (~b2);
}

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

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

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

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

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

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

static bset cho[576][256];
static void precomp() {
	for (int i = 0; i < 576; i++) {
		cho[i][0][0] = 1;
		for (int j = 1; j <= i && j < 256; j++) {
			cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
		}
	}
}

static bset 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();

	//find the rank of this one
	bset rnk = bset();
	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
			bset 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 & bset(255)).to_ulong();
		//printf(" %d", val);
		output(val);
		rnk >>= 8;
	}
	//printf("\n");
}

Compilation message (stderr)

encoder.cpp:63:13: warning: 'bool operator<=(bset, bset)' defined but not used [-Wunused-function]
 static bool operator <= (bset b1, bset b2) {
             ^~~~~~~~
encoder.cpp:59:13: warning: 'bool operator>(bset, bset)' defined but not used [-Wunused-function]
 static bool operator > (bset b1, bset b2) {
             ^~~~~~~~
encoder.cpp:38:13: warning: 'bset operator-(bset, bset)' defined but not used [-Wunused-function]
 static bset operator - (bset b1, bset b2) {
             ^~~~~~~~

decoder.cpp:63:13: warning: 'bool operator<=(bset, bset)' defined but not used [-Wunused-function]
 static bool operator <= (bset b1, bset b2) {
             ^~~~~~~~
decoder.cpp:59:13: warning: 'bool operator>(bset, bset)' defined but not used [-Wunused-function]
 static bool operator > (bset b1, bset b2) {
             ^~~~~~~~
decoder.cpp:55:13: warning: 'bool operator>=(bset, bset)' defined but not used [-Wunused-function]
 static bool operator >= (bset b1, bset b2) {
             ^~~~~~~~
decoder.cpp:38:13: warning: 'bset operator-(bset, bset)' defined but not used [-Wunused-function]
 static bset operator - (bset b1, bset b2) {
             ^~~~~~~~

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