oj.uz

Submission #330523

# Submission time Handle Problem Language Result Execution time Memory
330523 2020-11-25T15:38:27 Z cki86201 Parrots (IOI11_parrots) C++17
100 / 100
 343 ms 180348 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<90;i++)p[i]=0;}
	int p[90];
}nCr[700][700],I;
 
int E[300];
 
bignum Plus(bignum A,bignum B)
{
	bignum ret;
	ret.init();
	for(int i=0;i<89;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=89;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<700;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<90;i++)p[i]=0;}
	int p[90];
}dnCr[700][700],dI;
 
int D[300];
 
dbignum dPlus(dbignum A,dbignum B)
{
	dbignum ret;
	ret.init();
	for(int i=0;i<89;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=89;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<700;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 327 ms 179296 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 179444 KB Output is correct
2 Correct 320 ms 179744 KB Output is correct
3 Correct 319 ms 179480 KB Output is correct
4 Correct 323 ms 179452 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 179544 KB Output is correct
2 Correct 327 ms 179320 KB Output is correct
3 Correct 325 ms 179480 KB Output is correct
4 Correct 321 ms 179356 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 179624 KB Output is correct
2 Correct 322 ms 179324 KB Output is correct
3 Correct 321 ms 179476 KB Output is correct
4 Correct 327 ms 179732 KB Output is correct
5 Correct 334 ms 179616 KB Output is correct
6 Correct 329 ms 179728 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 179484 KB Output is correct - P = 5.000000
2 Correct 331 ms 179788 KB Output is correct - P = 5.000000
3 Correct 330 ms 179608 KB Output is correct - P = 5.000000
4 Correct 341 ms 179700 KB Output is correct - P = 5.000000
5 Correct 339 ms 179728 KB Output is correct - P = 5.000000
6 Correct 343 ms 180348 KB Output is correct - P = 5.000000
7 Correct 339 ms 179860 KB Output is correct - P = 5.000000