Submission #923231

#	Time	Username	Problem	Language	Result	Execution time	Memory
923231		daoquanglinh2007	Parrots (IOI11_parrots)	C++17	100 / 100	962 ms	14420 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
#define ll long long
#define vu vector <unsigned>
 
const int NM = 64;
const ll base = 1LL<<32;
 
int N, L, M[NM+5], X[5*NM+5];
vu dp[5*NM+5][256];

vu create(ll x){
	vu s = {};
	while (x > 0){
		s.push_back(x%base);
		x /= base;
	}
	if (s.empty()) s.push_back(0);
	reverse(s.begin(), s.end());
	return s;
}
 
ll decreate(vu s){
	ll x = 0;
	for (int i = 0; i < isz(s); i++)
		x = x*base+s[i];
	return x;
}
 
int cmp(vu a, vu b){
	if (isz(a) < isz(b)) return -1;
	if (isz(a) > isz(b)) return 1;
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
}
 
vu add(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	ll carry = 0;
	for (int i = 0; i < isz(a); i++){
		ll s = (ll)a[i]+b[i]+carry;
		c.push_back(s%base);
		carry = s/base;
	}
	if (carry > 0) c.push_back(1);
	reverse(c.begin(), c.end());
	return c;
}
 
vu sub(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	int borrow = 0;
	for (int i = 0; i < isz(a); i++){
		ll h = (ll)a[i]-b[i]-borrow;
		if (h < 0){
			h += base;
			borrow = 1;
		}
		else{
			borrow = 0;
		}
		c.push_back(h);
	}
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
void preprocess(){
	for (int i = 255; i >= 0; i--){
		dp[L][i] = create(256-i);
	}
	for (int i = L-1; i >= 1; i--)
		for (int j = 255; j >= 0; j--){
			dp[i][j] = dp[i+1][j];
			if (j < 255) dp[i][j] = add(dp[i][j], dp[i][j+1]);
		}
}
 
vu mul(vu a, ll b){
	vu c = {};
	ll carry = 0;
	for (int i = isz(a)-1; i >= 0; i--){
		ll s = (ll)a[i]*b+carry;
		c.push_back(s%base);
		carry = s/base;
	}
	while (carry > 0){
		c.push_back(carry%base);
		carry /= base;
	}
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
void trace(int i, vu s){
	if (i > L) return;
	for (int j = 255; j >= 0; j--){
		if (cmp(dp[i][j], s) >= 0){
			send(j);
			if (j < 255) s = sub(s, dp[i][j+1]);
			trace(i+1, s);
			return;
		}
	}
}
 
void encode(int _N, int _M[]){
	N = _N;
	L = 4*N+10;
	for (int i = 0; i < N; i++) M[i] = _M[i];
	
	preprocess();
	vu tmp = create(0);
	for (int i = 0; i < N; i++){
		tmp = add(mul(tmp, 256), create(M[i]));
	}
	tmp = add(tmp, create(1));
	trace(1, tmp);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
#define ll long long
#define vu vector <unsigned>
 
const int NM = 64;
const ll base = 1LL<<32;
 
int N, L, M[NM+5], X[5*NM+5];
vu dp[5*NM+5][256];

vu create(ll x){
	vu s = {};
	while (x > 0){
		s.push_back(x%base);
		x /= base;
	}
	if (s.empty()) s.push_back(0);
	reverse(s.begin(), s.end());
	return s;
}
 
ll decreate(vu s){
	ll x = 0;
	for (int i = 0; i < isz(s); i++)
		x = x*base+s[i];
	return x;
}
 
int cmp(vu a, vu b){
	if (isz(a) < isz(b)) return -1;
	if (isz(a) > isz(b)) return 1;
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
}
 
vu add(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	ll carry = 0;
	for (int i = 0; i < isz(a); i++){
		ll s = (ll)a[i]+b[i]+carry;
		c.push_back(s%base);
		carry = s/base;
	}
	if (carry > 0) c.push_back(1);
	reverse(c.begin(), c.end());
	return c;
}
 
vu sub(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	int borrow = 0;
	for (int i = 0; i < isz(a); i++){
		ll h = (ll)a[i]-b[i]-borrow;
		if (h < 0){
			h += base;
			borrow = 1;
		}
		else{
			borrow = 0;
		}
		c.push_back(h);
	}
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
void preprocess(){
	for (int i = 255; i >= 0; i--){
		dp[L][i] = create(256-i);
	}
	for (int i = L-1; i >= 1; i--)
		for (int j = 255; j >= 0; j--){
			dp[i][j] = dp[i+1][j];
			if (j < 255) dp[i][j] = add(dp[i][j], dp[i][j+1]);
		}
}
 
vu find_order(int i){
	if (i > L) return create(1);
	vu res = create(0);
	if (X[i] < 255) res = dp[i][X[i]+1];
	return add(res, find_order(i+1));
}
 
vu div(vu a, ll b){
	vu c = {};
	ll h = 0;
	for (int i = 0; i < isz(a); i++){
		h = (ll)h*base+a[i];
		c.push_back(h/b);
		h %= b;
	}
	reverse(c.begin(), c.end());
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
ll mod(vu a, ll b){
	ll h = 0;
	for (int i = 0; i < isz(a); i++){
		h = ((ll)h*base+a[i])%b;
	}
	return h;
}

void decode(int _N, int _L, int _X[]){
	N = _N;
	L = _L;
	for (int i = 1; i <= L; i++) X[i] = _X[i-1];
	sort(X+1, X+1+L);
	
	preprocess();
	
	vu tmp = sub(find_order(1), create(1));
	
	for (int i = N-1; i >= 0; i--){
		M[i] = mod(tmp, 256);
		tmp = div(tmp, 256);
	}
	
	for (int i = 0; i < N; i++) output(M[i]);
}

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