Submission #330525

#	Time	Username	Problem	Language	Result	Execution time	Memory
330525		cki86201	Parrots (IOI11_parrots)	C++17	100 / 100	219 ms	102764 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<algorithm>
using namespace std;
typedef long long ll;
 
struct bignum{
	bignum(){}
	void init(){for(int i=0;i<73;i++)p[i]=0;}
	int p[73];
}nCr[580][580],I;
 
int E[300];
 
bignum Plus(bignum A,bignum B)
{
	bignum ret;
	ret.init();
	for(int i=0;i<72;i++){
		ret.p[i] += A.p[i] + B.p[i];
		ret.p[i+1] += ret.p[i]>>8;
		ret.p[i] &= 0xff;
	}
	return ret;
}
 
bool comp(bignum A,bignum B)
{
	int i;
	for(i=72;i>=0;i--)if(A.p[i]!=B.p[i])return A.p[i]<B.p[i];
	return 0;
}
 
inline bignum nHr(int n,int r){return nCr[n+r-1][min(n-1,r)];}
 
void encode(int N, int M[])
{
	int i,j;
	if(!nCr[1][1].p[0]){
		for(i=0;i<580;i++){
			nCr[i][0].p[0]=1;
			nCr[i][i].p[0]=1;
			for(j=1;j<i;j++)nCr[i][j] = Plus(nCr[i-1][j],nCr[i-1][j-1]);
		}
	}
	for(i=N-1;i>=0;i--)I.p[i] = M[i];
	int R = 5*N;
	bignum tmp;
	tmp.init();
	for(i=0;i<256;i++){
		for(j=0;j<=R;j++){
			bignum tmp2 = Plus(tmp,nHr(256-i,R-j));
			if(comp(I,tmp2))break;
			tmp = tmp2;
		}
		E[i]=j;
		R-=j;
	}
	for(i=0;i<256;i++){
		for(j=0;j<E[i];j++)send(i);
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
 
#include<algorithm>
using namespace std;
 
 
struct dbignum{
	dbignum(){}
	void init(){for(int i=0;i<73;i++)p[i]=0;}
	int p[73];
}dnCr[580][580],dI;
 
int D[300];
 
dbignum dPlus(dbignum A,dbignum B)
{
	dbignum ret;
	ret.init();
	for(int i=0;i<72;i++){
		ret.p[i] += A.p[i] + B.p[i];
		ret.p[i+1] += ret.p[i]>>8;
		ret.p[i] &= 0xff;
	}
	return ret;
}
 
bool dcomp(dbignum A,dbignum B)
{
	int i;
	for(i=72;i>=0;i--)if(A.p[i]!=B.p[i])return A.p[i]<B.p[i];
	return 0;
}
 
inline dbignum dnHr(int n,int r){return dnCr[n+r-1][min(n-1,r)];}
 
void decode(int N, int L, int X[])
{
	int i,j;
	if(!dnCr[1][1].p[0]){
		for(i=0;i<580;i++){
			dnCr[i][0].p[0]=1;
			dnCr[i][i].p[0]=1;
			for(j=1;j<i;j++)dnCr[i][j] = dPlus(dnCr[i-1][j],dnCr[i-1][j-1]);
		}
	}
	for(i=0;i<256;i++)D[i]=0;
	for(i=0;i<L;i++)D[X[i]]++;
	int R = 5*N;
	dbignum tmp;
	tmp.init();
	for(i=0;i<256;i++){
		for(j=0;j<D[i];j++){
			tmp = dPlus(tmp,dnHr(256-i,R-j));
		}
		R-=j;
	}
	for(i=0;i<N;i++)output(tmp.p[i]);
}

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