Submission #124357

#	Time	Username	Problem	Language	Result	Execution time	Memory
124357		nxteru	Parrots (IOI11_parrots)	C++14	100 / 100	13 ms	1784 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void encode(int N, int M[]){
	ll n,dp[40][40],rs=0;
	for(int i=0;i<40;i++)for(int j=0;j<40;j++)dp[i][j]=0;
	n=N;
	for(int i=0;i<27;i++)dp[0][i]=1LL;
	for(int i=1;i<35;i++){
		for(int j=0;j<27;j++){
			for(int k=0;k<=j;k++){
				dp[i][j]+=dp[i-1][k];
			}
		}
	}
	for(int i=0;i<35;i++){
		for(int j=1;j<27;j++){
			dp[i][j]+=dp[i][j-1];
		}
	}
	for(int i=0;i<n;i+=7){
		ll s=0,p=0;
		for(int j=i;j<n&&j<i+7;j++,p++){
			s*=256LL;
			s+=ll(M[j]);
		}
		p*=5LL;
		s++;
		for(int j=p-1;j>=0;j--){
			for(int k=0;k<min(256LL-rs,27LL);k++){
				if(dp[j][k]>=s){
					send(rs+k);
					if(k>0)s-=dp[j][k-1];
					break;
				}
			}
		}
		rs+=27LL;
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void decode(int N, int L, int X[]){
	ll n,l,dp[40][40],rs=0,xs=0;
	for(int i=0;i<40;i++)for(int j=0;j<40;j++)dp[i][j]=0;
	n=N,l=L;
	sort(X,X+l);
	for(int i=0;i<27;i++)dp[0][i]=1LL;
	for(int i=1;i<35;i++){
		for(int j=0;j<27;j++){
			for(int k=0;k<=j;k++){
				dp[i][j]+=dp[i-1][k];
			}
		}
	}
	for(int i=0;i<35;i++){
		for(int j=1;j<27;j++){
			dp[i][j]+=dp[i][j-1];
		}
	}
	for(int i=0;i<n;i+=7){
		ll s=0,p=0;
		for(int j=i;j<n&&j<i+7;j++,p++);
		p*=5LL;
		for(int j=p-1;j>=0;j--){
			if(X[xs+j]-rs>0)s+=dp[j][X[xs+j]-rs-1];
		}
		xs+=p;
		rs+=27LL;
		p/=5LL;
		for(ll i=p-1;i>=0;i--)output((s>>(i*8LL))&255LL);
	}
}

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