Submission #96261

#	Time	Username	Problem	Language	Result	Execution time	Memory
96261		Noam527	Parrots (IOI11_parrots)	C++17	Compilation error	0 ms	0 KiB

encoder

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;

struct bigint {
	const int lim = 1000000, lg = 6;
	vector<int> a;
	bigint(int val = 0) {
		a.clear();
		a.push_back(val);
		clear();
	}
	bigint(vector<int> &b) {
		a = b;
		clear();
	}
	void clear() {
		int s = 0;
		for (int i = 0; i < a.size(); i++) {
			a[i] += s;
			s = a[i] / lim;
			a[i] %= lim;
			if (a[i] < 0) {
				s--;
				a[i] += lim;
			}
		}
		while (s > 0) {
			a.push_back(s % lim);
			s /= lim;
		}
		while (a.size() > 1 && a.back() == 0) a.pop_back();
	}
	int operator [](int k) const {
		return a[k];
	}
	int size() const {
		return a.size();
	}
	void operator = (const bigint &b) {
		a = b.a;
		clear();
	}

	bigint operator + (const bigint &b) const {
		vector<int> c(max((int)a.size(), b.size()));
		for (int i = 0; i < a.size() || i < b.size(); i++) {
			c[i] = 0;
			if (i < a.size()) c[i] += a[i];
			if (i < b.size()) c[i] += b[i];
		}
		return bigint(c);
	}
	void operator += (const bigint &b) {
		for (int i = 0; i < b.size(); i++) {
			if (i >= a.size()) a.push_back(0);
			a[i] += b[i];
		}
		clear();
	}
	void operator += (int val) {
		a[0] += val;
		clear();
	}
	bigint operator - (const bigint &b) const {
		vector<int> c(max((int)a.size(), b.size()));
		for (int i = 0; i < a.size() || i < b.size(); i++) {
			c[i] = 0;
			if (i < a.size()) c[i] += a[i];
			if (i < b.size()) c[i] -= b[i];
		}
		return bigint(c);
	}
	void operator -= (const bigint &b) {
		for (int i = 0; i < b.size(); i++) {
			if (i >= a.size()) a.push_back(0);
			a[i] -= b[i];
		}
		clear();
	}
	void operator -= (int val) {
		a[0] -= val;
		clear();
	}
	void operator *= (int val) {
		for (int i = 0; i < a.size(); i++) a[i] *= val;
		clear();
	}
	bool operator < (const bigint &b) const {
		if (a.size() != b.size()) return a.size() < b.size();
		for (int i = (int)a.size() - 1; i >= 0; i--)
			if (a[i] != b[i]) return a[i] < b[i];
		return false;
	}
	bool operator > (const bigint &b) const {
		if (a.size() != b.size()) return a.size() > b.size();
		for (int i = (int)a.size() - 1; i >= 0; i--)
			if (a[i] != b[i]) return a[i] > b[i];
		return false;
	}
};

const int lim1 = 259, lim2 = 333;
bigint dp[lim1][lim2]; // number of 0's, number of 1's
bigint pw[70][256]; // pw[i][j] = 256^i * j

void preprocess() {
	for (int i = 0; i < lim1; i++)
		dp[i][0] = bigint(1);
	for (int j = 0; j < lim2; j++)
		dp[0][j] = bigint(1);
	for (int i = 1; i < lim1; i++) for (int j = 1; j < lim2; j++)
		dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

	for (int i = 0; i < 256; i++) pw[0][i] = bigint(i);
	for (int i = 1; i < 70; i++) {
		pw[i][0] = bigint(0);
		pw[i][1] = bigint(pw[i - 1][255] + pw[i - 1][1]);
		for (int j = 2; j < 256; j++)
			pw[i][j] = pw[i][1] + pw[i][j - 1];
	}
}
vector<int> tocount(vector<int> &a) {
	int n = 5 * (int)a.size();
	bigint code(0);
	for (const auto &i : a) {
		code *= 256;
		code += i;
	}
//	cout << "code\n";
//	for (const auto &i : code.a) cout << i << " "; cout << '\n';
	vector<int> cnt(257, 0);
	int left = 256;
	while (left > 0 && n > 0) {
		if (code < dp[left - 1][n]) {
			left--;
		}
		else {
			code -= dp[left - 1][n];
			cnt[left]++;
			n--;
		}
	}
	while (n > 0) {
		cnt[left]++;
		n--;
	}
//	cout << "after adding:\n";
//	cout << "code\n";
//	for (const auto &i : code.a) cout << i << " "; cout << '\n';
	return cnt;
}
vector<int> tovector(int origsz, vector<int> c) {
	int n = 0, nn = origsz;
	bigint code(0);
	int left = 0;
	while (c[left] > 0) {
		c[left]--;
		n++;
	}
	while (left <= 256) {
		while (c[left] > 0) {
			n++;
			c[left]--;
			code += dp[left - 1][n];
//			cout << "adding " << left - 1 << " " << n << '\n';
		}
		left++;
	}
//	cout << "code\n";
//	for (const auto &i : code.a) cout << i << " "; cout << '\n';
	n = nn;
	vector<int> rtn(n, -1);
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 255; j >= 0; j--) {
			if (!(pw[i][j] > code)) {
				code -= pw[i][j];
				rtn[n - 1 - i] = j;
				break;
			}
		}
	}
	return rtn;
}
#include "encoder.h"
#include "manager.h"
/*
void send(int a) {
	cout << a << " ";
}
*/
void encode(vector<int> M) {
	if (dp[0][0].a[0] != 1) {
		preprocess();
	}
	M = tocount(M);
	for (int i = 0; i < 256; i++)
		for (int j = 0; j < M[i]; j++)
			send(i);
}
/*
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &i : a) cin >> i;
	encode(a);
}
*/

decoder

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;

struct bigint2 {
	const int lim = 1000000, lg = 6;
	vector<int> a;
	bigint2(int val = 0) {
		a.clear();
		a.push_back(val);
		clear();
	}
	bigint2(vector<int> &b) {
		a = b;
		clear();
	}
	void clear() {
		int s = 0;
		for (int i = 0; i < a.size(); i++) {
			a[i] += s;
			s = a[i] / lim;
			a[i] %= lim;
			if (a[i] < 0) {
				s--;
				a[i] += lim;
			}
		}
		while (s > 0) {
			a.push_back(s % lim);
			s /= lim;
		}
		while (a.size() > 1 && a.back() == 0) a.pop_back();
	}
	int operator [](int k) const {
		return a[k];
	}
	int size() const {
		return a.size();
	}
	void operator = (const bigint2 &b) {
		a = b.a;
		clear();
	}

	bigint2 operator + (const bigint2 &b) const {
		vector<int> c(max((int)a.size(), b.size()));
		for (int i = 0; i < a.size() || i < b.size(); i++) {
			c[i] = 0;
			if (i < a.size()) c[i] += a[i];
			if (i < b.size()) c[i] += b[i];
		}
		return bigint2(c);
	}
	void operator += (const bigint2 &b) {
		for (int i = 0; i < b.size(); i++) {
			if (i >= a.size()) a.push_back(0);
			a[i] += b[i];
		}
		clear();
	}
	void operator += (int val) {
		a[0] += val;
		clear();
	}
	bigint2 operator - (const bigint2 &b) const {
		vector<int> c(max((int)a.size(), b.size()));
		for (int i = 0; i < a.size() || i < b.size(); i++) {
			c[i] = 0;
			if (i < a.size()) c[i] += a[i];
			if (i < b.size()) c[i] -= b[i];
		}
		return bigint2(c);
	}
	void operator -= (const bigint2 &b) {
		for (int i = 0; i < b.size(); i++) {
			if (i >= a.size()) a.push_back(0);
			a[i] -= b[i];
		}
		clear();
	}
	void operator -= (int val) {
		a[0] -= val;
		clear();
	}
	void operator *= (int val) {
		for (int i = 0; i < a.size(); i++) a[i] *= val;
		clear();
	}
	bool operator < (const bigint2 &b) const {
		if (a.size() != b.size()) return a.size() < b.size();
		for (int i = (int)a.size() - 1; i >= 0; i--)
			if (a[i] != b[i]) return a[i] < b[i];
		return false;
	}
	bool operator > (const bigint2 &b) const {
		if (a.size() != b.size()) return a.size() > b.size();
		for (int i = (int)a.size() - 1; i >= 0; i--)
			if (a[i] != b[i]) return a[i] > b[i];
		return false;
	}
};

const int lim3 = 259, lim4 = 333;
bigint2 dp2[lim3][lim4]; // number of 0's, number of 1's
bigint2 pw2[70][256]; // pw2[i][j] = 256^i * j

void preprocess2() {
	for (int i = 0; i < lim3; i++)
		dp2[i][0] = bigint2(1);
	for (int j = 0; j < lim4; j++)
		dp2[0][j] = bigint2(1);
	for (int i = 1; i < lim3; i++) for (int j = 1; j < lim4; j++)
		dp2[i][j] = dp2[i - 1][j] + dp2[i][j - 1];

	for (int i = 0; i < 256; i++) pw2[0][i] = bigint2(i);
	for (int i = 1; i < 70; i++) {
		pw2[i][0] = bigint2(0);
		pw2[i][1] = bigint2(pw2[i - 1][255] + pw2[i - 1][1]);
		for (int j = 2; j < 256; j++)
			pw2[i][j] = pw2[i][1] + pw2[i][j - 1];
	}
}
vector<int> tocount2(vector<int> &a) {
	int n = 5 * (int)a.size();
	bigint2 code(0);
	for (const auto &i : a) {
		code *= 256;
		code += i;
	}
	//	cout << "code\n";
	//	for (const auto &i : code.a) cout << i << " "; cout << '\n';
	vector<int> cnt(257, 0);
	int left = 256;
	while (left > 0 && n > 0) {
		if (code < dp2[left - 1][n]) {
			left--;
		}
		else {
			code -= dp2[left - 1][n];
			cnt[left]++;
			n--;
		}
	}
	while (n > 0) {
		cnt[left]++;
		n--;
	}
	//	cout << "after adding:\n";
	//	cout << "code\n";
	//	for (const auto &i : code.a) cout << i << " "; cout << '\n';
	return cnt;
}
vector<int> tovector2(int origsz, vector<int> c) {
	int n = 0, nn = origsz;
	bigint2 code(0);
	int left = 0;
	while (c[left] > 0) {
		c[left]--;
		n++;
	}
	while (left <= 256) {
		while (c[left] > 0) {
			n++;
			c[left]--;
			code += dp2[left - 1][n];
			//			cout << "adding " << left - 1 << " " << n << '\n';
		}
		left++;
	}
	//	cout << "code\n";
	//	for (const auto &i : code.a) cout << i << " "; cout << '\n';
	n = nn;
	vector<int> rtn(n, -1);
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 255; j >= 0; j--) {
			if (!(pw2[i][j] > code)) {
				code -= pw2[i][j];
				rtn[n - 1 - i] = j;
				break;
			}
		}
	}
	return rtn;
}
#include "decoder.h"
#include "manager.h"
/*
void output(int b) {
	cout << b << " ";
}
*/
void decode(int N, vector<int> X) {
	if (dp2[0][0].a[0] != 1) {
		preprocess2();
	}
	vector<int> cnt(257, 0);
	for (auto &i : X) cnt[i]++;
	X = tovector2(N, cnt);
	for (auto &i : X) output(i);
}
/*
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> x(m);
	for (auto &i : x) cin >> i;
	decode(n, x);
}
*/

Compilation message (stderr)

encoder.cpp:191:10: fatal error: manager.h: No such file or directory
 #include "manager.h"
          ^~~~~~~~~~~
compilation terminated.

decoder.cpp:191:10: fatal error: manager.h: No such file or directory
 #include "manager.h"
          ^~~~~~~~~~~
compilation terminated.