Submission #961400

#	Time	Username	Problem	Language	Result	Execution time	Memory
961400		emptypringlescan	Parrots (IOI11_parrots)	C++17	63 / 100	12 ms	1676 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
void encode(int n, int m[]){
	if(n>=16) for(int i=0; i<(int)(1.7*n); i++) send(255);
	mt19937 rng(177013);
	int t=n*8,cnt=0;
	for(int i=0; i<n; i++){
		for(int j=7; j>=0; j--){
			if(m[i]>>j&1) cnt++;
		}
	}
	int num=0,x=0;
	if(cnt==t/2){
		while(true){
			num++;
			x=rng()%t;
			if(m[x/8]>>(x%8)&1){
				m[x/8]^=1<<(x%8);
				for(int i=0; i<num+1; i++) send(255);
				break;
			}
		}
	}
	int prev=0;
	if(cnt<=t/2){
		for(int i=0; i<n; i++){
			for(int j=0; j<8; j++){
				if(m[i]>>j&1){
					prev++;
					send(prev);
				}
				else send(prev);
			}
		}
	}
	else{
		for(int i=0; i<n; i++){
			for(int j=0; j<8; j++){
				if(!(m[i]>>j&1)){
					prev++;
					send(prev);
				}
				else send(prev);
			}
		}
		send(255);
	}
	if(num) m[x/8]^=1<<(x%8);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
void decode(int n, int l, int x[]){
	sort(x,x+l);
	assert(l>=8*n);
	mt19937 rng(177013);
	if(n>=16) l-=(int)(1.7*n);
	int bits[8*n],ex=l-8*n;
	if(ex==1){
		int prev=0;
		for(int i=0; i<8*n; i++){
			bits[i]=x[i]-prev;
			prev=x[i];
			bits[i]^=1;
		}
	}
	else{
		int prev=0;
		for(int i=0; i<8*n; i++){
			bits[i]=x[i]-prev;
			prev=x[i];
		}
		if(ex>0){
			int y=0;
			for(int i=0; i<ex-1; i++) y=rng()%(8*n);
			//cout << y << ' ';
			bits[y]^=1;
		}
	}
	for(int i=0; i<n; i++){
		int ret=0;
		for(int j=0; j<8; j++){
			ret+=bits[i*8+j]<<j;
		}
		output(ret);
	}
}

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