oj.uz

Submission #859

# Submission time Handle Problem Language Result Execution time Memory
859 2013-04-25T12:35:10 Z gs12117 Parrots (IOI11_parrots) C++
100 / 100
 125 ms 44512 KB 
#include "encoder.h"
#include "encoderlib.h"
int ecom[280][280][70];
void encode(int N, int M[])
{
	int i,j,k;
	int slist[280];
	int mlist[70];
	int tmp[70];
	if(ecom[0][0][0]==0){
		ecom[0][0][0]=1;
		for(i=0;i<275;i++){
			for(j=0;j<275;j++){
				for(k=0;k<69;k++){
					if(i!=0)ecom[i][j][k]+=ecom[i-1][j][k];
					if(j!=0)ecom[i][j][k]+=ecom[i][j-1][k];
					if(ecom[i][j][k]>255){
						ecom[i][j][k+1]=ecom[i][j][k]>>8;
						ecom[i][j][k]&=255;
					}
				}
			}
		}
	}
	for(i=0;i<N;i++){
		mlist[i]=M[i];
	}
	for(i=N;i<70;i++){
		mlist[i]=0;
	}
	k=256;
	for(i=0;i<270;){
		for(j=0;j<70;j++){
			tmp[j]=0;
		}
		for(j=0;j<69;j++){
			tmp[j]+=mlist[j]-ecom[269-i][k][j];
			while(tmp[j]<0){
				tmp[j+1]--;
				tmp[j]+=256;
			}
		}
		if(tmp[69]==-1){
			slist[i]=k;
			i++;
		}
		else{
			for(j=0;j<70;j++){
				mlist[j]=tmp[j];
			}
			k--;
		}
	}
	for(i=0;i<270;i++){
		if(slist[i]!=256){
			send(slist[i]);
		}
	}
}

#include "decoder.h"
#include "decoderlib.h"
int dcom[280][280][70];
void decode(int N, int L, int X[])
{
	int i,j,k;
	int slist[280];
	int mlist[70];
	if(dcom[0][0][0]==0){
		dcom[0][0][0]=1;
		for(i=0;i<275;i++){
			for(j=0;j<275;j++){
				for(k=0;k<69;k++){
					if(i!=0)dcom[i][j][k]+=dcom[i-1][j][k];
					if(j!=0)dcom[i][j][k]+=dcom[i][j-1][k];
					if(dcom[i][j][k]>255){
						dcom[i][j][k+1]=dcom[i][j][k]>>8;
						dcom[i][j][k]&=255;
					}
				}
			}
		}
	}
	for(i=0;i<270-L;i++){
		slist[i]=256;
	}
	for(i=0;i<L;i++){
		slist[i+270-L]=X[i];
	}
	for(i=0;i<270;i++){
		for(j=0;j<i;j++){
			if(slist[i]>slist[j]){
				k=slist[i];
				slist[i]=slist[j];
				slist[j]=k;
			}
		}
	}
	for(i=0;i<70;i++){
		mlist[i]=0;
	}
	for(i=269;i>0;i--){
		for(j=slist[i]+1;j<=slist[i-1];j++){
			for(k=0;k<70;k++){
				mlist[k]+=dcom[269-i][j][k];
				if(mlist[k]>255){
					mlist[k+1]+=mlist[k]>>8;
					mlist[k]&=255;
				}
			}
		}
	}
	for(i=0;i<N;i++){
		output(mlist[i]);
	}
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 43048 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 43976 KB Output is correct
2 Correct 102 ms 43976 KB Output is correct
3 Correct 98 ms 44080 KB Output is correct
4 Correct 100 ms 44080 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 44080 KB Output is correct
2 Correct 101 ms 44456 KB Output is correct
3 Correct 102 ms 44456 KB Output is correct
4 Correct 106 ms 44456 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 44456 KB Output is correct
2 Correct 125 ms 44456 KB Output is correct
3 Correct 108 ms 44456 KB Output is correct
4 Correct 107 ms 44456 KB Output is correct
5 Correct 115 ms 44456 KB Output is correct
6 Correct 104 ms 44456 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 44456 KB Output is correct - P = 1.750000
2 Correct 107 ms 44456 KB Output is correct - P = 2.437500
3 Correct 108 ms 44512 KB Output is correct - P = 2.484848
4 Correct 112 ms 44512 KB Output is correct - P = 3.280000
5 Correct 115 ms 44512 KB Output is correct - P = 3.833333
6 Correct 115 ms 44512 KB Output is correct - P = 4.015873
7 Correct 112 ms 44512 KB Output is correct - P = 4.078125