Submission #782841

#	Time	Username	Problem	Language	Result	Execution time	Memory
782841		sentheta	Parrots (IOI11_parrots)	C++17	100 / 100	319 ms	14396 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(0) cout << "?" << #x << " : " << (x) << endl << flush;

static const int A = 10;
static const int B = 60;
// 600 bit integer
// least significant bits are Int[A-1]
// most significant bits are Int[0]
#define Int array<long long,A>
static Int operator+(Int a,Int b){
	Int ret;
	rep(i,0,A){
		ret[i] = a[i]+b[i];
	}
	for(int i=A-1; i>=0; i--) if(ret[i] > (1LL<<B)){
		ret[i] -= 1LL<<B;
		ret[i-1]++;
	}
	return ret;
}
static Int operator-(Int a,Int b){
	for(int i=A-1; i>=0; i--){
		if(a[i] < b[i]){
			a[i-1]--;
			a[i] += 1LL<<B;
		}
		a[i] -= b[i];
	}
	return a;
}
static void print(Int a){
	return;
	rep(i,0,A) cout << a[i] << " ";
	cout << nl;
}

static const int N = 256;
static const int LEN = 325;
static Int dp[LEN][N];
static void buildDP(){
	rep(i,0,LEN) rep(j,0,N){
		rep(k,0,A) dp[i][j] [k]=0;
	}
	for(int x=0; x<N; x++){
		dp[1][x] [A-1]=1;
	}
	for(int i=2; i<LEN; i++){
		dp[i][0] = dp[i-1][0];
		for(int x=1; x<N; x++){
			dp[i][x] = dp[i-1][x] + dp[i][x-1];
		}
	}
}



// #########################

void encode(int n,int m[]){
	buildDP();

	Int v;
	rep(i,0,A) v[i] = 0;
	for(int i=0; i<n; i++){
		for(int b=0; b<8; b++) if(m[i]&1LL<<b){
			int p = 8*i+b;
			v[A-1 - p/B] |= 1LL<<(p%B);
		}
	}
	print(v);

	dbg(n);

	int len = 1;
	while(dp[len][255] < v) len++;

	for(int i=len; i>=1; i--){
		int x = 0;
		while(dp[i][x] < v) x++;
		assert(v<dp[i][x] || v==dp[i][x]);

		if(x > 0){
			v = v - dp[i][x-1];
		}

		dbg(i);
		dbg(x);
		print(dp[i][x-1]);
		print(v);
		// cout << nl;

		send(x);
	}
	print(v);
	// rep(i,0,A) assert(v[i]==0);

	// cout << "END" << nl << nl << nl;



}

decoder

#include "decoder.h"
#include "decoderlib.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(0) cout << "?" << #x << " : " << (x) << endl << flush;


static const int A = 10;
static const int B = 60;
// 600 bit integer
// least significant bits are Int[A-1]
// most significant bits are Int[0]
#define Int array<long long,A>
static Int operator+(Int a,Int b){
	Int ret;
	rep(i,0,A){
		ret[i] = a[i]+b[i];
	}
	for(int i=A-1; i>=0; i--) if(ret[i] > (1LL<<B)){
		ret[i] -= 1LL<<B;
		ret[i-1]++;
	}
	return ret;
}
static Int operator-(Int a,Int b){
	for(int i=A-1; i>=0; i--){
		if(a[i] < b[i]){
			a[i-1]--;
			a[i] += 1LL<<B;
		}
		a[i] -= b[i];
	}
	return a;
}
static void print(Int a){
	return;
	rep(i,0,A) cout << a[i] << " ";
	cout << nl;
}

static const int N = 256;
static const int LEN = 325;
static Int dp[LEN][N];
static void buildDP(){
	rep(i,0,LEN) rep(j,0,N){
		rep(k,0,A) dp[i][j] [k]=0;
	}
	for(int x=0; x<N; x++){
		dp[1][x] [A-1]=1;
	}
	for(int i=2; i<LEN; i++){
		dp[i][0] = dp[i-1][0];
		for(int x=1; x<N; x++){
			dp[i][x] = dp[i-1][x] + dp[i][x-1];
		}
	}
}


// #########################

void decode(int n,int len,int a[]){
	buildDP();
	sort(a, a+len);
	
	Int one;
	rep(i,0,A) one[i] = 0;
	one[A-1] = 1;

	Int v;
	rep(i,0,A) v[i] = 0;
	v[A-1] = 0;

	bool nonZro = 0;

	dbg(len);
	for(int i=len; i>=1; i--){
		int x = a[i-1];
		nonZro |= x!=0;
		if(x > 0){
			v = v + dp[i][x-1];
		}
		else{
			// v = v + one;
		}
		dbg(x);
	}
	if(nonZro) v = v+one;
	print(v);

	for(int i=0; i<n; i++){
		int x = 0;
		for(int b=0; b<8; b++){
			int p = 8*i+b;
			if(v[A-1 - p/B]&1LL<<(p%B)){
				x |= 1LL<<b;
			}
		}

		dbg(i);
		dbg(x);
		output(x);
	}

}

Compilation message (stderr)

decoder.cpp:46:12: warning: 'std::array<long long int, 10> operator-(std::array<long long int, 10>, std::array<long long int, 10>)' defined but not used [-Wunused-function]
   46 | static Int operator-(Int a,Int b){
      |            ^~~~~~~~

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