oj.uz

Submission #48992

# Submission time Handle Problem Language Result Execution time Memory
48992 2018-05-21T06:17:25 Z Namnamseo Parrots (IOI11_parrots) C++17
100 / 100
 13 ms 2976 KB 
#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);
		}
	}
}


#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 868 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2016 KB Output is correct
2 Correct 6 ms 2080 KB Output is correct
3 Correct 7 ms 2416 KB Output is correct
4 Correct 6 ms 2528 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2528 KB Output is correct
2 Correct 6 ms 2528 KB Output is correct
3 Correct 7 ms 2528 KB Output is correct
4 Correct 6 ms 2528 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2528 KB Output is correct
2 Correct 7 ms 2528 KB Output is correct
3 Correct 7 ms 2528 KB Output is correct
4 Correct 8 ms 2528 KB Output is correct
5 Correct 8 ms 2528 KB Output is correct
6 Correct 8 ms 2528 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2672 KB Output is correct - P = 5.000000
2 Correct 9 ms 2672 KB Output is correct - P = 5.000000
3 Correct 9 ms 2672 KB Output is correct - P = 5.000000
4 Correct 11 ms 2816 KB Output is correct - P = 5.000000
5 Correct 12 ms 2840 KB Output is correct - P = 5.000000
6 Correct 13 ms 2976 KB Output is correct - P = 5.000000
7 Correct 13 ms 2976 KB Output is correct - P = 5.000000