Submission #859

#	Time	Username	Problem	Language	Result	Execution time	Memory
859		gs12117	Parrots (IOI11_parrots)	C++98	100 / 100	125 ms	44512 KiB

encoder

#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]);
		}
	}
}

decoder

#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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19