oj.uz

Submission #330525

# Submission time Handle Problem Language Result Execution time Memory
330525 2020-11-25T15:49:39 Z cki86201 Parrots (IOI11_parrots) C++17
100 / 100
 219 ms 102764 KB 
#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);
	}
}
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 101704 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 101744 KB Output is correct
2 Correct 192 ms 102168 KB Output is correct
3 Correct 188 ms 102008 KB Output is correct
4 Correct 190 ms 101888 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 102152 KB Output is correct
2 Correct 195 ms 101896 KB Output is correct
3 Correct 195 ms 101944 KB Output is correct
4 Correct 191 ms 102080 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 101744 KB Output is correct
2 Correct 192 ms 101880 KB Output is correct
3 Correct 193 ms 101936 KB Output is correct
4 Correct 198 ms 102124 KB Output is correct
5 Correct 199 ms 101896 KB Output is correct
6 Correct 196 ms 102136 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 101752 KB Output is correct - P = 5.000000
2 Correct 198 ms 102368 KB Output is correct - P = 5.000000
3 Correct 201 ms 102220 KB Output is correct - P = 5.000000
4 Correct 202 ms 102108 KB Output is correct - P = 5.000000
5 Correct 206 ms 102052 KB Output is correct - P = 5.000000
6 Correct 219 ms 102764 KB Output is correct - P = 5.000000
7 Correct 209 ms 102056 KB Output is correct - P = 5.000000