Submission #676787

#	Time	Username	Problem	Language	Result	Execution time	Memory
676787		Alan	Parrots (IOI11_parrots)	C++17	0 / 100	1572 ms	45212 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct BigInt {
	static const ll unit = 1000000000, digit = 9;
	vector<ll> x {0};
	BigInt () {}
	BigInt (vector<ll> y) {
		x = y;
	}
	BigInt (ll y) {
		x.resize(3);
		x[0] = y%unit;
		x[1] = y/unit%unit;
		x[2] = y/unit/unit;
		while (x.back() == 0 && (int) x.size() > 1) x.pop_back();
	}
	BigInt operator+ (BigInt y) {
		BigInt tmp = BigInt(x);
		if (y.x.size() < tmp.x.size()) swap(y, tmp);
		for (int i = 0; i < (int) tmp.x.size(); i++) y.x[i] += tmp.x[i];
		y.x.push_back(0);
		for (int i = 0; i < (int) y.x.size()-1; i++) if (y.x[i] >= 1e9) {
			y.x[i+1] += y.x[i]/unit;
			y.x[i] %= unit;
		}
		if ((int) y.x.size() > 1 && y.x.back() == 0) y.x.pop_back();
		return y;
	}
	BigInt operator* (BigInt y) {
		BigInt tmp = BigInt(x), res (0);
		res.x.resize(y.x.size()+tmp.x.size()+1);
		for (int i = 0; i < (int) y.x.size(); i++) for (int j = 0; j < (int) tmp.x.size(); j++) res.x[i+j] += y.x[i]*tmp.x[j];
		for (int i = 0; i < (int) res.x.size()-1; i++) if (res.x[i] >= 1e9) {
			res.x[i+1] += res.x[i]/unit;
			res.x[i] %= unit;
		}
		while ((int) res.x.size() > 1 && res.x.back() == 0) res.x.pop_back();
		return res;
	}
	bool operator== (BigInt y) {
		if (x.size() != y.x.size()) return false;
		for (int i = 0; i < (int) x.size(); i++) if (x[i] != y.x[i]) return false;
		return true;
	}
	bool operator<= (BigInt y) {
		if (x.size() < y.x.size()) return true;
		if (x.size() > y.x.size()) return false;
		for (int i = (int) x.size()-1; i >= 0; i--) {
			if (x[i] < y.x[i]) return true;
			if (x[i] > y.x[i]) return false;
		}
		return true;
	}
};
 
BigInt pow (BigInt x, ll p) {
	if (!p) return BigInt(1);
	BigInt t = pow(x, p/2);
	t = t*t;
	return p % 2 == 1 ? t * x : t;
}
 
ostream& operator<< (ostream& o, BigInt x) {
	string s;
	for (int i = (int) x.x.size() - 1; i >= 0; i--) {
		if (i != (int) x.x.size() - 1) for (int j = 0; j < x.digit - (int) to_string(x.x[i]).size(); j++) s.push_back('0');
		s += to_string(x.x[i]);
	}
	return o << s;
}
 
BigInt ncr[600][350];
 
void precomp () {
	for (int i = 0; i < 600; i++) for (int j = 0; j <= min(i, 349); j++) {
		if (j == 0 || j == i) ncr[i][j] = BigInt(1);
		else ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
	}
}
 
void encode (int n, int m[]) {
	precomp();
	BigInt res (0), rep (0);
	for (int i = 0; i < n; i++) res = res + BigInt(m[i]) * pow(BigInt(256), i);
	int last = 0;
	for (int i = 0; i < n*5; i++) {
		if (i == n*5-1) {
			for (int j = 0; j < 256; j++) if (rep+BigInt(j) == res) {
				send(last+j);
				break;
			}
			break;
		}
		while (rep + ncr[254-last+n*5-i][n*5-i-1] <= res) {
			rep = rep + ncr[254-last+n*5-i][n*5-i-1];
			last++;
		}
		send(last);
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct BigInt {
	static const ll unit = 1000000000, digit = 9;
	vector<ll> x {0};
	BigInt () {}
	BigInt (vector<ll> y) {
		x = y;
	}
	BigInt (ll y) {
		x.resize(3);
		x[0] = y%unit;
		x[1] = y/unit%unit;
		x[2] = y/unit/unit;
		while (x.back() == 0 && (int) x.size() > 1) x.pop_back();
	}
	BigInt operator+ (BigInt y) {
		BigInt tmp = BigInt(x);
		if (y.x.size() < tmp.x.size()) swap(y, tmp);
		for (int i = 0; i < (int) tmp.x.size(); i++) y.x[i] += tmp.x[i];
		y.x.push_back(0);
		for (int i = 0; i < (int) y.x.size()-1; i++) if (y.x[i] >= 1e9) {
			y.x[i+1] += y.x[i]/unit;
			y.x[i] %= unit;
		}
		if ((int) y.x.size() > 1 && y.x.back() == 0) y.x.pop_back();
		return y;
	}
	BigInt operator* (BigInt y) {
		BigInt tmp = BigInt(x), res (0);
		res.x.resize(y.x.size()+tmp.x.size()+1);
		for (int i = 0; i < (int) y.x.size(); i++) for (int j = 0; j < (int) tmp.x.size(); j++) res.x[i+j] += y.x[i]*tmp.x[j];
		for (int i = 0; i < (int) res.x.size()-1; i++) if (res.x[i] >= 1e9) {
			res.x[i+1] += res.x[i]/unit;
			res.x[i] %= unit;
		}
		while ((int) res.x.size() > 1 && res.x.back() == 0) res.x.pop_back();
		return res;
	}
	bool operator== (BigInt y) {
		if (x.size() != y.x.size()) return false;
		for (int i = 0; i < (int) x.size(); i++) if (x[i] != y.x[i]) return false;
		return true;
	}
	bool operator<= (BigInt y) {
		if (x.size() < y.x.size()) return true;
		if (x.size() > y.x.size()) return false;
		for (int i = (int) x.size()-1; i >= 0; i--) {
			if (x[i] < y.x[i]) return true;
			if (x[i] > y.x[i]) return false;
		}
		return true;
	}
};
 
BigInt pow (BigInt x, ll p) {
	if (!p) return BigInt(1);
	BigInt t = pow(x, p/2);
	t = t*t;
	return p % 2 == 1 ? t * x : t;
}
 
ostream& operator<< (ostream& o, BigInt x) {
	string s;
	for (int i = (int) x.x.size() - 1; i >= 0; i--) {
		if (i != (int) x.x.size() - 1) for (int j = 0; j < x.digit - (int) to_string(x.x[i]).size(); j++) s.push_back('0');
		s += to_string(x.x[i]);
	}
	return o << s;
}
 
BigInt ncr[600][350];
 
void precomp () {
	for (int i = 0; i < 600; i++) for (int j = 0; j <= min(i, 349); j++) {
		if (j == 0 || j == i) ncr[i][j] = BigInt(1);
		else ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
	}
}
 
void decode (int n, int l, int x[]) {
	BigInt res (0), rep (0);
	vector<int> ans (n);
	sort(x, x+l);
	for (int i = x[l-2]; i < x[l-1]; i++) res = res + 1;
	int last = 0;
	for (int i = 0; i < l-1; i++) for (; last < x[i]; last++) res = res + ncr[254-last+n*5-i][n*5-i-1];
	for (int i = n-1; i >= 0; i--) {
		while (rep + BigInt(ans[i]+1) * pow(BigInt(256), i) <= res) ans[i]++;
		rep = rep + BigInt(ans[i]) * pow(BigInt(256), i);
	}
	for (int i = 0; i < n; i++) output(ans[i]);
}

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