oj.uz

Submission #4633

# Submission time Handle Problem Language Result Execution time Memory
4633 2013-11-13T11:44:32 Z cki86201 Parrots (IOI11_parrots) C++
0 / 100
 193 ms 180840 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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 178864 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 Runtime error 180 ms 180128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 178 ms 180128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 193 ms 180488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 180488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 184 ms 180552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 183 ms 180632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 187 ms 180632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 189 ms 180632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 192 ms 180664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 191 ms 180840 KB Execution killed with signal 11 (could be triggered by violating memory limits)