Submission #96264

#	Time	Username	Problem	Language	Result	Execution time	Memory
96264		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"

void send(int 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"

void output(int 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: In member function 'void bigint::clear()':
encoder.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) {
                   ~~^~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator+(const bigint&) const':
encoder.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size() || i < b.size(); i++) {
                   ~~^~~~~~~~~~
encoder.cpp:54:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < a.size()) c[i] += a[i];
        ~~^~~~~~~~~~
encoder.cpp: In member function 'void bigint::operator+=(const bigint&)':
encoder.cpp:61:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i >= a.size()) a.push_back(0);
        ~~^~~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator-(const bigint&) const':
encoder.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size() || i < b.size(); i++) {
                   ~~^~~~~~~~~~
encoder.cpp:74:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < a.size()) c[i] += a[i];
        ~~^~~~~~~~~~
encoder.cpp: In member function 'void bigint::operator-=(const bigint&)':
encoder.cpp:81:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i >= a.size()) a.push_back(0);
        ~~^~~~~~~~~~~
encoder.cpp: In member function 'void bigint::operator*=(int)':
encoder.cpp:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) a[i] *= val;
                   ~~^~~~~~~~~~
encoder.cpp: In member function 'bool bigint::operator<(const bigint&) const':
encoder.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() < b.size();
       ~~~~~~~~~^~~~~~~~~~~
encoder.cpp:95:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() < b.size();
                                    ~~~~~~~~~^~~~~~~~~~
encoder.cpp: In member function 'bool bigint::operator>(const bigint&) const':
encoder.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() > b.size();
       ~~~~~~~~~^~~~~~~~~~~
encoder.cpp:101:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() > b.size();
                                    ~~~~~~~~~^~~~~~~~~~
/tmp/ccqqvcRO.o: In function `main':
grader_encoder.cpp:(.text.startup+0x141): undefined reference to `encode(int, int*)'
collect2: error: ld returned 1 exit status

decoder.cpp: In member function 'void bigint2::clear()':
decoder.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) {
                   ~~^~~~~~~~~~
decoder.cpp: In member function 'bigint2 bigint2::operator+(const bigint2&) const':
decoder.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size() || i < b.size(); i++) {
                   ~~^~~~~~~~~~
decoder.cpp:54:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < a.size()) c[i] += a[i];
        ~~^~~~~~~~~~
decoder.cpp: In member function 'void bigint2::operator+=(const bigint2&)':
decoder.cpp:61:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i >= a.size()) a.push_back(0);
        ~~^~~~~~~~~~~
decoder.cpp: In member function 'bigint2 bigint2::operator-(const bigint2&) const':
decoder.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size() || i < b.size(); i++) {
                   ~~^~~~~~~~~~
decoder.cpp:74:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < a.size()) c[i] += a[i];
        ~~^~~~~~~~~~
decoder.cpp: In member function 'void bigint2::operator-=(const bigint2&)':
decoder.cpp:81:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i >= a.size()) a.push_back(0);
        ~~^~~~~~~~~~~
decoder.cpp: In member function 'void bigint2::operator*=(int)':
decoder.cpp:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) a[i] *= val;
                   ~~^~~~~~~~~~
decoder.cpp: In member function 'bool bigint2::operator<(const bigint2&) const':
decoder.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() < b.size();
       ~~~~~~~~~^~~~~~~~~~~
decoder.cpp:95:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() < b.size();
                                    ~~~~~~~~~^~~~~~~~~~
decoder.cpp: In member function 'bool bigint2::operator>(const bigint2&) const':
decoder.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() > b.size();
       ~~~~~~~~~^~~~~~~~~~~
decoder.cpp:101:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a.size() != b.size()) return a.size() > b.size();
                                    ~~~~~~~~~^~~~~~~~~~
/tmp/ccEOd7AF.o: In function `main':
grader_decoder.cpp:(.text.startup+0x1f6): undefined reference to `decode(int, int, int*)'
collect2: error: ld returned 1 exit status