oj.uz

Submission #4632

# Submission time Handle Problem Language Result Execution time Memory
4632 2013-11-13T11:40:31 Z cki86201 Parrots (IOI11_parrots) C++
0 / 100
 2000 ms 179216 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;
	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;
	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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1251 ms 179216 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 89948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 89996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 90020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 90020 KB Time limit exceeded
2 Execution timed out 2066 ms 90040 KB Time limit exceeded
3 Execution timed out 2071 ms 90192 KB Time limit exceeded
4 Execution timed out 2075 ms 90192 KB Time limit exceeded
5 Execution timed out 2074 ms 90192 KB Time limit exceeded
6 Execution timed out 2068 ms 90192 KB Time limit exceeded
7 Execution timed out 2052 ms 90192 KB Time limit exceeded