Submission #584377

#	Time	Username	Problem	Language	Result	Execution time	Memory
584377		benson1029	Parrots (IOI11_parrots)	C++14	100 / 100	7 ms	1360 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;

namespace encoder_var {
	long long ncr[50][50];

	void init() {
		for(int i=0; i<50; i++) {
			ncr[i][0] = ncr[i][i] = 1;
			for(int j=1; j<i; j++) {
				ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
			}
		}
	}

	long long nhr(int n, int r) {
		return ncr[n+r-1][r];
	}
};

void encode(int N, int M[])
{
	using namespace encoder_var;
	init();
	for(int i=0; i<N; i+=4) {
		int init = i*4;
		long long v = 0;
		for(int j=i+3; j>=i; j--) {
			v *= 256;
			if(j < N) v += M[j];
		}
		int prevv = 0;
		for(int j=0; j<20; j++) {
			int ans = 0;
			for(int k=prevv; k<=16; k++) {
				if(v < nhr(16-k+1, 20-j-1)) {
					ans = k;
					break;
				}
				v -= nhr(16-k+1, 20-j-1);
			}
			if(ans > 0) {
				send(init+ans-1);
			}
			prevv = ans;
		}
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;

namespace decoder_var {
	long long ncr[50][50];
	vector<int> tmp;
	int a[1000];

	void init() {
		for(int i=0; i<50; i++) {
			ncr[i][0] = ncr[i][i] = 1;
			for(int j=1; j<i; j++) {
				ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
			}
		}
	}

	long long nhr(int n, int r) {
		return ncr[n+r-1][r];
	}
};

void decode(int N, int L, int X[])
{
	using namespace decoder_var;
	sort(X, X+L);
	init();
	int ptr = 0;
	for(int i=0; i<64; i+=4) {
		int init = i*4;
		tmp.clear();
		while(ptr<L && X[ptr]<init+16) {
			tmp.push_back(X[ptr]-init+1);
			++ptr;
		}
		while(tmp.size() < 20) tmp.push_back(0);
		sort(tmp.begin(), tmp.end());
		int prevv = 0;
		long long ans = 0;
		for(int j=0; j<tmp.size(); j++) {
			for(int k=prevv; k<tmp[j]; k++) {
				ans += nhr(16-k+1, 20-j-1);
			}
			prevv = tmp[j];
		}
		for(int j=i; j<i+4; j++) {
			a[j] = ans % 256;
			ans /= 256;
		}
	}
	for(int i=0; i<N; i++) output(a[i]);
}

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int j=0; j<tmp.size(); j++) {
      |                ~^~~~~~~~~~~

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