Submission #923124

#	Time	Username	Problem	Language	Result	Execution time	Memory
923124		daoquanglinh2007	Parrots (IOI11_parrots)	C++17	100 / 100	1960 ms	18784 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
const int NM = 64, base = 128;
 
int N, L, M[NM+5], X[5*NM+5];
string dp[5*NM+5][256];
 
string create(int x){
	string s = "";
	while (x > 0){
		s = char(x%base)+s;
		x /= base;
	}
	if (s == "") s.push_back(0);
	return s;
}
 
int decreate(string s){
	int x = 0;
	for (int i = 0; i < isz(s); i++)
		x = x*base+s[i];
	return x;
}
 
int cmp(string a, string 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;
}
 
string add(string a, string 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);
	string c = "";
	int carry = 0;
	for (int i = 0; i < isz(a); i++){
		int s = 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;
}
 
string sub(string a, string 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);
	string c = "";
	int borrow = 0;
	for (int i = 0; i < isz(a); i++){
		int h = (int)a[i]-(int)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.erase(isz(c)-1, 1);
	reverse(c.begin(), c.end());
	return c;
}
 
void preprocess(){
	for (int i = 255; i >= 0; i--){
		dp[5*N][i] = create(256-i);
	}
	for (int i = 5*N-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]);
		}
}
 
string mul(string a, int b){
	string c = "";
	int carry = 0;
	for (int i = isz(a)-1; i >= 0; i--){
		int s = 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.erase(isz(c)-1, 1);
	reverse(c.begin(), c.end());
	return c;
}
 
void trace(int i, string s){
	if (i > 5*N) 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;
	for (int i = 0; i < N; i++) M[i] = _M[i];
	
	preprocess();
	string 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);
}
 
string find_order(int i){
	if (i > 5*N) return create(1);
	string res = create(0);
	if (X[i] < 255) res = dp[i][X[i]+1];
	return add(res, find_order(i+1));
}
 
string div(string a, int b){
	string c = "";
	int h = 0;
	for (int i = 0; i < isz(a); i++){
		h = 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.erase(isz(c)-1, 1);
	reverse(c.begin(), c.end());
	return c;
}
 
int mod(string a, int b){
	string c = "";
	int h = 0;
	for (int i = 0; i < isz(a); i++){
		h = (h*base+a[i])%b;
	}
	return h;
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
const int NM = 64, base = 128;
 
int N, L, M[NM+5], X[5*NM+5];
string dp[5*NM+5][256];
 
string create(int x){
	string s = "";
	while (x > 0){
		s = char(x%base)+s;
		x /= base;
	}
	if (s == "") s.push_back(0);
	return s;
}
 
int decreate(string s){
	int x = 0;
	for (int i = 0; i < isz(s); i++)
		x = x*base+s[i];
	return x;
}
 
int cmp(string a, string 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;
}
 
string add(string a, string 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);
	string c = "";
	int carry = 0;
	for (int i = 0; i < isz(a); i++){
		int s = 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;
}
 
string sub(string a, string 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);
	string c = "";
	int borrow = 0;
	for (int i = 0; i < isz(a); i++){
		int h = (int)a[i]-(int)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.erase(isz(c)-1, 1);
	reverse(c.begin(), c.end());
	return c;
}
 
void preprocess(){
	for (int i = 255; i >= 0; i--){
		dp[5*N][i] = create(256-i);
	}
	for (int i = 5*N-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]);
		}
}
 
string mul(string a, int b){
	string c = "";
	int carry = 0;
	for (int i = isz(a)-1; i >= 0; i--){
		int s = 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.erase(isz(c)-1, 1);
	reverse(c.begin(), c.end());
	return c;
}
 
string find_order(int i){
	if (i > 5*N) return create(1);
	string res = create(0);
	if (X[i] < 255) res = dp[i][X[i]+1];
	return add(res, find_order(i+1));
}
 
string div(string a, int b){
	string c = "";
	int h = 0;
	for (int i = 0; i < isz(a); i++){
		h = 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.erase(isz(c)-1, 1);
	reverse(c.begin(), c.end());
	return c;
}
 
int mod(string a, int b){
	string c = "";
	int h = 0;
	for (int i = 0; i < isz(a); i++){
		h = (h*base+a[i])%b;
	}
	return h;
}
 
void decode(int _N, int _L, int _X[]){
	N = _N;
	L = _L;
	for (int i = 5*N; i >= 1; i--) X[i] = _X[i-1];
	sort(X+1, X+1+5*N);
	
	preprocess();
	
	string 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