Submission #106285

#	Time	Username	Problem	Language	Result	Execution time	Memory
106285		tincamatei	Parrots (IOI11_parrots)	C++14	100 / 100	269 ms	168216 KiB

encoder

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

using namespace std;

const int MAX_DIGITS = 64;
const int BASE = 256;

struct HugeNumber {
	int nr[MAX_DIGITS];

	HugeNumber() {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = 0;
	}
	HugeNumber(int x) {
		for(int i = 0; i < MAX_DIGITS; ++i) {
			nr[i] = x % BASE;
			x /= BASE;
		}
	}

	HugeNumber operator+(const HugeNumber &x) const {
		HugeNumber rez;
		int t = 0;

		for(int i = 0; i < MAX_DIGITS; ++i) {
			t = (t + x.nr[i] + nr[i]);
			rez.nr[i] = t % BASE;
			t /= BASE;
		}

		return rez;
	}

	HugeNumber operator++() {
		int i = 0;
		while(i < MAX_DIGITS && nr[i] == BASE - 1) {
			nr[i] = 0;
			++i;
		}
		if(i < MAX_DIGITS)
			nr[i]++;
		return *this;
	}

	void operator=(const HugeNumber &x) {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = x.nr[i];
	}

	HugeNumber operator~() const {
		HugeNumber rez;

		for(int i = 0; i < MAX_DIGITS; ++i)
			rez.nr[i] = BASE - nr[i] - 1;
		return rez;
	}

	HugeNumber operator-(const HugeNumber &x) const {
		HugeNumber y = ~x;
		++y;

		return *this + y;
	}

	bool operator>= (const HugeNumber &x) const {
		int i = MAX_DIGITS - 1;
		
		while(i > 0 && nr[i] == x.nr[i])
			--i;
		return nr[i] >= x.nr[i];
	}
};

void putHuge(HugeNumber x) {
	for(int i = 4; i >= 0; --i)
		printf("(%d)", x.nr[i]);
	printf(" ");
}

const int MAX_COMB = 575;

HugeNumber comb[1+MAX_COMB][1+MAX_COMB];
bool initted = false;

void initCommon() {
	if(!initted) {
		initted = true;
		for(int i = 0; i <= MAX_COMB; ++i)
			for(int j = 0; j <= i; ++j)
				if(i == j || j == 0)
					++comb[i][j];
				else
					comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
	}
}

vector<int> snb(HugeNumber x, int pigeons) {
	int numbers = 256;

	int n = pigeons + numbers - 1;
	int k = pigeons;

	vector<int> rez;
	while(n > 0) {
		if(x >= comb[n - 1][k]) {
			x = x - comb[n - 1][k];
			rez.push_back(numbers - 1);
			n--;
			k--;
		} else {
			numbers--;
			n--;
		}
	}
	return rez;
}

void encode(int N, int M[]) {
	initCommon();
	
	HugeNumber data;
	for(int i = N - 1; i >= 0; --i)
  	data.nr[i] = M[i];
	
	vector<int> pigeons;
	pigeons = snb(data, 5 * N);

	for(auto it: pigeons)
		send(it);
}

decoder

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

using namespace std;

namespace Decoder {

const int MAX_DIGITS = 64;
const int BASE = 256;

struct HugeNumber {
	int nr[MAX_DIGITS];

	HugeNumber() {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = 0;
	}
	HugeNumber(int x) {
		for(int i = 0; i < MAX_DIGITS; ++i) {
			nr[i] = x % BASE;
			x /= BASE;
		}
	}

	HugeNumber operator+(const HugeNumber &x) const {
		HugeNumber rez;
		int t = 0;

		for(int i = 0; i < MAX_DIGITS; ++i) {
			t = (t + x.nr[i] + nr[i]);
			rez.nr[i] = t % BASE;
			t /= BASE;
		}

		return rez;
	}

	HugeNumber operator++() {
		int i = 0;
		while(i < MAX_DIGITS && nr[i] == BASE - 1) {
			nr[i] = 0;
			++i;
		}
		if(i < MAX_DIGITS)
			nr[i]++;
		return *this;
	}

	void operator=(const HugeNumber &x) {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = x.nr[i];
	}

	HugeNumber operator~() const {
		HugeNumber rez;

		for(int i = 0; i < MAX_DIGITS; ++i)
			rez.nr[i] = BASE - nr[i] - 1;
		return rez;
	}

	HugeNumber operator-(const HugeNumber &x) const {
		HugeNumber y = ~x;
		++y;

		return *this + y;
	}

	bool operator>= (const HugeNumber &x) const {
		int i = MAX_DIGITS - 1;
		
		while(i > 0 && nr[i] == x.nr[i])
			--i;
		return nr[i] >= x.nr[i];
	}
};

void putHuge(HugeNumber x) {
	for(int i = 4; i >= 0; --i)
		printf("(%d)", x.nr[i]);
	printf(" ");
}

const int MAX_COMB = 575;

HugeNumber comb[1+MAX_COMB][1+MAX_COMB];
bool initted = false;

void initCommon() {
	if(!initted) {
		initted = true;
		for(int i = 0; i <= MAX_COMB; ++i)
			for(int j = 0; j <= i; ++j)
				if(i == j || j == 0)
					++comb[i][j];
				else
					comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
	}
}

vector<int> snb(HugeNumber x, int pigeons) {
	int numbers = 256;

	int n = pigeons + numbers - 1;
	int k = pigeons;

	vector<int> rez;
	while(n > 0) {
		if(x >= comb[n - 1][k]) {
			x = x - comb[n - 1][k];
			rez.push_back(numbers - 1);
			n--;
			k--;
		} else {
			numbers--;
			n--;
		}
	}
	return rez;
}

HugeNumber invSnB(vector<int> v) {
	int n = v.size() + 256 - 1, k = v.size();
	int numbers = 255, pigeons = 0;

	HugeNumber rez;

	while(n > 0) {
		if(pigeons < v.size() && v[pigeons] == numbers) {
			pigeons++;
			rez = rez + comb[n - 1][k];
			n--;
			k--;
		} else {
			numbers--;
			n--;
		}
	}
	return rez;
}

}

void decode(int N, int L, int X[]) {
	using namespace Decoder;
	initCommon();
  
	vector<int> pigeons;
	for(int i = 0; i < L; ++i)
		pigeons.push_back(X[i]);
	
	sort(pigeons.rbegin(), pigeons.rend());
	HugeNumber rez = invSnB(pigeons);

	for(int i = 0; i < N; ++i)
		output(rez.nr[i]);
}

Compilation message (stderr)

decoder.cpp: In function 'Decoder::HugeNumber Decoder::invSnB(std::vector<int>)':
decoder.cpp:130:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pigeons < v.size() && v[pigeons] == numbers) {
      ~~~~~~~~^~~~~~~~~~

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