Submission #18432

#	Time	Username	Problem	Language	Result	Execution time	Memory
18432		suhgyuho_william	Parrots (IOI11_parrots)	C++98	81 / 100	61 ms	40832 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <stdio.h>
#include <algorithm>

using namespace std;

// 256 H 261 > 256^64
int Ht[260][270][70];
int cntt[260][270];
int first;
int tmpt[70];

#define MOD 256

void sett(){
	int i,j,k;

	for(i=1; i<=256; i++){ cntt[i][0] = 1; Ht[i][0][1] = 1; }
	for(i=1; i<=256; i++){ cntt[i][1] = 1; Ht[i][1][1] = i; }
	for(i=1; i<=261; i++){ cntt[1][i] = 1; Ht[1][i][1] = 1; }
    for(i=2; i<=256; i++){
		for(j=2; j<=261; j++){
			for(k=1; k<=cntt[i][j-1]; k++) Ht[i][j][k] = Ht[i][j-1][k];
			for(k=1; k<=cntt[i-1][j]; k++) Ht[i][j][k] += Ht[i-1][j][k];
			for(k=1; k<=max(cntt[i][j-1],cntt[i-1][j]); k++){
				Ht[i][j][k+1] += (Ht[i][j][k] / MOD);
				Ht[i][j][k] %= MOD;
			}
			for(k=max(cntt[i][j-1],cntt[i-1][j])+1; ; k++){
				if(Ht[i][j][k] == 0) break;
				Ht[i][j][k+1] = (Ht[i][j][k] / MOD);
				Ht[i][j][k] %= MOD;
			}
			cntt[i][j] = k-1;
		}
    }
}

int comp(int n,int m,int len){
	if(cntt[n][m] > len) return -1;
	if(cntt[n][m] < len) return 1;
	int i;
	for(i=cntt[n][m]; i>=1; i--){
		if(Ht[n][m][i] > tmpt[i]) return -1;
		if(Ht[n][m][i] < tmpt[i]) return 1;
	}
	return 0;
}

void process(int N,int M[]){
    int i,j,tt;
    int tmp[100];
    int bit[100];

    for(i=0; i<N; i++) tmp[i] = M[i];
    int dp[10][10][10][10];
    int a,b,c,d;
    int cnt = -1;
    struct data{
        int a,b,c,d;
    }memo[500];

    for(tt=0; tt<=7; tt++) for(a=0; a<=tt; a++) for(b=0; b<=tt-a; b++) for(c=0; c<=tt-a-b; c++){cnt++;  d = tt-a-b-c;dp[a][b][c][d] = cnt;  memo[cnt].a = a;memo[cnt].b = b;memo[cnt].c = c;memo[cnt].d = d;    }
    for(i=0; i<=cnt; i++) if(memo[i].a+memo[i].b+memo[i].c+memo[i].d > 7) printf("!");
    for(i=0; i<N; i++){
        cnt = M[i];
        for(j=1; j<=memo[cnt].a; j++) send(i*4+0);
        for(j=1; j<=memo[cnt].b; j++) send(i*4+1);
        for(j=1; j<=memo[cnt].c; j++) send(i*4+2);
        for(j=1; j<=memo[cnt].d; j++) send(i*4+3);
    }
    for(i=0; i<N; i++) M[i] = tmp[i];
}

void encode(int N, int M[]){
	if(N <= 32){
		process(N,M);
		return;
	}
	int i,j,k;
	int x,sum,len;

	first++;
	if(first == 1) sett();

	len = N;
	for(i=1; i<=N; i++) tmpt[i] = 255;
	for(i=1; i<=261; i++){
		if(comp(256,i,len) <= 0) break;
	}
	x = sum = i;
	for(i=0; i<N; i++) tmpt[i+1] = M[i];
	len = N;
	for(i=256; i>=2; i--){
		for(j=0; j<=x; j++){
			if(comp(i-1,x-j,len) < 0) break;
			for(k=1; k<=cntt[i-1][x-j]; k++){
				tmpt[k] -= Ht[i-1][x-j][k];
				if(tmpt[k] < 0){
					tmpt[k] += MOD;
					tmpt[k+1]--;
				}
			}
			for(k=cntt[i][j]+1; k<=len; k++){
				if(tmpt[k] < 0){
					tmpt[k] += MOD;
					tmpt[k+1]--;
				}else break;
			}
			for(k=len; k>=1; k--){
				if(tmpt[k] != 0) break;
			}
			len = k;
		}
		for(k=0; k<j; k++) send(i-1);
		x -= j;
	}
	for(i=1; i<=tmpt[1]; i++) send(0);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

int H[260][270][70];
int cnt[260][270];
int tmp[70];

#define MOD 256

void setting(){
	int i,j,k;

	for(i=1; i<=256; i++){ cnt[i][0] = 1; H[i][0][1] = 1; }
	for(i=1; i<=256; i++){ cnt[i][1] = 1; H[i][1][1] = i; }
	for(i=1; i<=261; i++){ cnt[1][i] = 1; H[1][i][1] = 1; }
    for(i=2; i<=256; i++){
		for(j=2; j<=261; j++){
			for(k=1; k<=cnt[i][j-1]; k++) H[i][j][k] = H[i][j-1][k];
			for(k=1; k<=cnt[i-1][j]; k++) H[i][j][k] += H[i-1][j][k];
			for(k=1; k<=max(cnt[i][j-1],cnt[i-1][j]); k++){
				H[i][j][k+1] += (H[i][j][k] / MOD);
				H[i][j][k] %= MOD;
			}
			for(k=max(cnt[i][j-1],cnt[i-1][j])+1; ; k++){
				if(H[i][j][k] == 0) break;
				H[i][j][k+1] = (H[i][j][k] / MOD);
				H[i][j][k] %= MOD;
			}
			cnt[i][j] = k-1;
		}
    }
}

int compare(int n,int m,int len){
	if(cnt[n][m] > len) return -1;
	if(cnt[n][m] < len) return 1;
	int i;
	for(i=cnt[n][m]; i>=1; i--){
		if(H[n][m][i] > tmp[i]) return -1;
		if(H[n][m][i] < tmp[i]) return 1;
	}
	return 0;
}

int firsttime;
int many[260];
int ans[100];

void process(int N,int L,int X[]){
    int i,j;
    int t1,t2;
    int ans[100];
    int tmp[100][4];
    int dp[10][10][10][10];
    int a,b,c,d,tt;
    int cnt = -1;

    for(tt=0; tt<=7; tt++){
        for(a=0; a<=tt; a++) for(b=0; b<=tt-a; b++) for(c=0; c<=tt-a-b; c++){ cnt++; d = tt-a-b-c; dp[a][b][c][d] = cnt; }
    }
    for(i=0; i<N; i++) for(j=0; j<4; j++) tmp[i][j] = 0;
    for(i=0; i<L; i++){  t1 = X[i] / 4; t2 = X[i] % 4; tmp[t1][t2]++; }
    for(i=0; i<N; i++) ans[i] = 0;
    for(i=0; i<N; i++){
        ans[i] = dp[tmp[i][0]][tmp[i][1]][tmp[i][2]][tmp[i][3]];
    }
    for(i=0; i<N; i++) output(ans[i]);
}

void decode(int N, int L, int X[]){
	if(N <= 32){
		process(N,L,X);
		return;
	}
	int i,j,k;
	int x,sum,len;

	firsttime++;
	if(firsttime == 1) setting();
	for(i=1; i<=N; i++) tmp[i] = 255;
	len = N;
	for(i=1; i<=261; i++){
		if(compare(256,i,len) <= 0) break;
	}
	x = sum = i;
	for(i=0; i<256; i++) many[i] = 0;
	for(i=0; i<L; i++) many[X[i]]++;
	for(i=1; i<=N; i++) ans[i] = 0;
	for(i=255; i>=1; i--){
		if(many[i] == 0) continue;
		for(j=0; j<many[i]; j++){
			for(k=1; k<=cnt[i][x-j]; k++) ans[k] += H[i][x-j][k];
		}
		x -= many[i];
	}
	ans[1] += many[0];
	for(k=1; k<N; k++){
		ans[k+1] += (ans[k]/256);
		ans[k] %= 256;
	}
	for(k=1; k<=N; k++) output(ans[k]);
}

Compilation message (stderr)

encoder.cpp: In function 'void process(int, int*)':
encoder.cpp:54:9: warning: unused variable 'bit' [-Wunused-variable]
     int bit[100];
         ^~~
encoder.cpp:57:9: warning: variable 'dp' set but not used [-Wunused-but-set-variable]
     int dp[10][10][10][10];
         ^~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 0 / 19