Submission #250952

#	Time	Username	Problem	Language	Result	Execution time	Memory
250952		kostia244	Parrots (IOI11_parrots)	C++17	100 / 100	11 ms	1792 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
namespace g {
	ll c[69][69]; 
	vi kth(ll l, ll k, ll o) {
		vi ans;
		while(l--) {
			if(o < c[l][k]) ans.push_back(0);
			else o-=c[l][k--],ans.push_back(1);
		}
		return ans;
	}
};
void bad(int n, int b[]) {
	vector<int> m[2];
	for(int f = 0; f < 2; f++)
	for(int i = 0; i < n; i++) {
		int t = b[i], g = 0;
		if(f) t ^= 255;
		while(t) {
			while(t&3) {
				m[f].push_back(4*i + g);
				t--;
			}
			t>>=2;
			g++;
		}
	}
	for(int i = 0; i < n; i++) m[1].push_back(69);
	if(m[0].size() > m[1].size()) swap(m[0], m[1]);
	for(auto i : m[0]) send(i);
}
void encode(int n, int b[]) {
	if(n < 16) {bad(n, b);return;}
	using namespace g;
	vi l;
	int i,j,bias=0;
	for(i = 0; i < 64; i++)
		for(j = 0; j <= i; j++)
			c[i][j] = j?c[i-1][j]+c[i-1][j-1]:1;
	for(i =0;i<1<<18;i++) {
		int s = 5*(i&63);
		s+=((i/64)&63)*6;
		s+=(i>>12)*7;
		if(s==n)break;
	}
	for(j=5;i;i>>=6,j++)
		while(i&63) --i,l.push_back(j);
	i=j=0;
	for(auto t : l){
		ll k = 0, l = t;
		//cout << t << '\n';
		while(t--){
			k = k*256 + b[i++];
		//	cout << b[i-1] << "-\n ";
		}
		//cout << k << "8==========d\n";
		
		for(auto i : kth(9*l - 1, 5*l, k)) {
			if(i == 0) bias++;
			else send(bias);
			//cout << i << " ";
		}
		bias++;
		//cout << "DONE\n";
		++j;
	}
	//cout << "orz\n";
	//cout << '\n';
	
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
namespace v {
	ll c[69][69]; 
	ll id(vi cur) {
		ll a = 0, n = cur.size(), k = count(cur.begin(), cur.end(), 1);
		for(int l = 0; l < n; l++)
			if(cur[l]) a += c[n-l-1][k], k--;
		return a;
	}
};
void bad(int n, int l, int X[]) {
	vector<int> res(n);
	map<int, int> cnt;
	for(int i = 0; i < l; i++) cnt[X[i]]++;
	int rev = 0;
	for(auto i : cnt) {
		if(i.second >= n) i.second -= n, rev = 255;
		res[i.first/4] += i.second<<(2*(i.first&3));
	}
	for(int i = 0; i < n; i++) output(res[i]^rev);
}
void decode(int n, int L, int b[]) {
	if(n < 16) {bad(n, L, b);return;}
	using namespace v;
	vi l,res(n);
	ll k,i,j;
	for(i = 0; i < 64; i++)
		for(j = 0; j <= i; j++)
			c[i][j] = j?c[i-1][j]+c[i-1][j-1]:1;
	for(i =0;i<1<<18;i++) {
		int s = 5*(i&63);
		s+=((i/64)&63)*6;
		s+=(i>>12)*7;
		if(s==n)break;
	}
	for(j=5;i;i>>=6,j++)
		while(i&63) --i,l.push_back(j);
	sort(b, b+L);
	//for(int i = 0; i < L; i++) cout << b[i] << " "; cout << '\n';
	for(k=i=j=0;i<l.size();k+=l[i++]){
		//cout << "\t" << l[i]*4 << '\n';
		int d,p = 0;
		vi cur;
		//cerr << p << "DKJKFSDJKSFDD\n";
		while(j < L && b[j]-4*k < 4*l[i]) {
			b[j] -= 4*k;
			d = b[j]-p;
			//cout << j << " " << L << " " << b[j] << " " << p << '\n';
			p = b[j];
			while(d--) cur.push_back(0);
			cur.push_back(1);
			j++;
		}
		//cout << j << "//" << l[i] << ":(\n";
		//for(auto i : cur) cout << i << " ";cout << "nDun\n";
		while(cur.size() < 9*l[i]-1) cur.push_back(0), p++;
		//for(auto i : cur) cout << i << " ";cout << "Dun\n";
		ll t = id(cur);
		//cout << t << '\n';
		for(int p = k+l[i]; p-- > k;) res[p] = t&255, t/=256;
	}
	for(auto i : res) output(i);
}

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(k=i=j=0;i<l.size();k+=l[i++]){
              ~^~~~~~~~~
decoder.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(cur.size() < 9*l[i]-1) cur.push_back(0), p++;
         ~~~~~~~~~~~^~~~~~~~~~

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