Submission #48992

#	Time	Username	Problem	Language	Result	Execution time	Memory
48992		Namnamseo	Parrots (IOI11_parrots)	C++17	100 / 100	13 ms	2976 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
//#include <cstdio>
#include <vector>
using namespace std;

typedef unsigned long long ll;
static int each_cnt[256];

static ll combi[72][72];
static bool big[72][72];

static void bC(){
	combi[0][0]=1;
	for(int i=1; i<=71; ++i){
		combi[i][0]=combi[i][i]=1;
		for(int j=1; j<i; ++j){
			combi[i][j]=combi[i-1][j-1]+combi[i-1][j];
			if(i==68){
				if(31<=j && j<=37) big[i][j]=true;
			}
			if(i==69){
				if(29<=j && j<=40) big[i][j]=true;
			}
			if(i==70){
				if(28<=j && j<=42) big[i][j]=true;
			}
			if(i==71){
				if(27<=j && j<=44) big[i][j]=true;
			}
		}
	}
}

static void procChunk(int *st, int count,int chL,int chR){
	ll index = 0;
	for(int i=0; i<count; ++i){
		index *= 256;
		index += st[i];
	}
//	printf("ENC Index %llu\n",index);
	int ones = chR - chL;
	int left_count = 5*count + ones;
	vector<int> v;
	for(;left_count;){
		if(index >= combi[left_count-1][ones] && !big[left_count-1][ones]){
			//printf("Index %lld; combi %lld\n",index,combi[left_count-1][ones]);

			index -= combi[left_count-1][ones];
			--ones;
			v.push_back(1);
			left_count -= 1;
		} else {
			v.push_back(0);
			left_count -= 1;
		}
	}
	auto it=v.begin();
	for(int i=chL; it!=v.end(); ++it){
		if((*it) == 0){
			++each_cnt[i];
		} else {
			++i;
		}
	}
}

int min(int a,int b){ return a>b?b:a; }

//#include <cstdio>
void encode(int N, int A[])
{
	if(!combi[0][0]) bC();
	for(int i=0; i<256; ++i) each_cnt[i]=0;
	for(int i=0; i<N; i += 8){
		procChunk(A+i, min(N-i, 8), i*4, i*4+31);
	}
	for(int i=0; i<256; ++i){
		int t=each_cnt[i];
		//if(t) printf("Send %d: times %d\n", i, t);
		for(;t--;){
			send(i);
		}
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
//#include <cstdio>
#include <vector>
using namespace std;

typedef unsigned long long ll;
static int cnt_each[256];

static ll combi[72][72];
static bool big[72][72];

static void bC(){
	combi[0][0]=1;
	for(int i=1; i<=71; ++i){
		combi[i][0]=combi[i][i]=1;
		for(int j=1; j<i; ++j){
			combi[i][j]=combi[i-1][j-1]+combi[i-1][j];
			if(i==68){
				if(31<=j && j<=37) big[i][j]=true;
			}
			if(i==69){
				if(29<=j && j<=40) big[i][j]=true;
			}
			if(i==70){
				if(28<=j && j<=42) big[i][j]=true;
			}
			if(i==71){
				if(27<=j && j<=44) big[i][j]=true;
			}
		}
	}
}

static void procChunk(int *st, int count,int chL,int chR){
	vector<int> v;
	for(int i=chL; i<=chR; ++i){
		//if(cnt_each[i]) printf("Receiving: %d, %d\n", i, cnt_each[i]);
		for(int j=0; j<cnt_each[i]; ++j) v.push_back(0);
		if(i<chR) v.push_back(1);
	}
	ll index = 0;
	int ones = chR-chL;
	for(int i=0; i<v.size(); ++i){
		if(v[i] == 1){
			index += combi[((int)v.size())-1-i][ones];
			--ones;
		}
	}
	//printf("DEC Index %llu\n", index);
	for(int i=0; i<count; ++i){
		st[count-1-i] = index%256;
		index /= 256;
	}
}

static int min(int a,int b){ return a>b?b:a; }

void decode(int N, int L, int X[])
{
	if(!combi[0][0]) bC();
	for(int i=0; i<256; ++i) cnt_each[i] = 0;

	for(int i=0; i<L; ++i) ++cnt_each[X[i]];

	int rets[N];
	for(int i=0; i<N; ++i) rets[i]=0;

	for(int i=0; i<N; i += 8){
		procChunk(rets+i, min(N-i, 8), i*4, i*4+31);
	}
	for(int i=0; i<N; ++i) output(rets[i]);
}

Compilation message (stderr)

decoder.cpp: In function 'void procChunk(int*, int, int, int)':
decoder.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); ++i){
               ~^~~~~~~~~

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