Submission #1146142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146142		SmuggingSpun	Parrots (IOI11_parrots)	C++20	81 / 100	3 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
void encode(int N, int M[]){
	if(N <= 32){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < 8; j++){
				if(1 << j & M[i]){
					send((i << 3) + j);
				}
			}
		}
		return;
	}
	mt19937 rng(123);
	vector<vector<int>>rd_hash(N, vector<int>(256));
	for(int i = 0; i < N; i++){
		iota(rd_hash[i].begin(), rd_hash[i].end(), 0);
		shuffle(rd_hash[i].begin(), rd_hash[i].end(), rng);
	}
	int cnt_bit = 0;
	for(int i = 0; i < N; i++){
		cnt_bit += __builtin_popcount(rd_hash[i][M[i]]);
	}
	int p = 0;
	auto send_bit = [&] (int x){
		if(x > 0){
			send(p);
		}	
		else{
			p++;
		}
	};
	int need_swap = int(cnt_bit < (N << 2));
	send_bit(need_swap);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 8; j++){
			send_bit((rd_hash[i][M[i]] >> j & 1) ^ need_swap);
		}
	}
	cout << endl;
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
void decode(int N, int L, int X[]){
	if(N <= 32){
		vector<bool>bit(N << 3, false);
		for(int i = 0; i < L; i++){
			bit[X[i]] = true;
		}
		for(int i = 0; i < N; i++){
			int ans = 0;
			for(int j = 0; j < 8; j++){
				if(bit[(i << 3) + j]){
					ans |= 1 << j;
				}
			}
			output(ans);
		}
		return;
	}
	mt19937 rng(123);
	vector<vector<int>>rd_hash(N, vector<int>(256));
	for(int i = 0; i < N; i++){
		iota(rd_hash[i].begin(), rd_hash[i].end(), 0);
		shuffle(rd_hash[i].begin(), rd_hash[i].end(), rng);
	}
	vector<int>cnt(600, 0);
	int p = 0;
	for(int i = 0; i < L; i++){
		cnt[X[i]]++;
	}
	auto get_bit = [&] (){
		if(cnt[p] > 0){
			cnt[p]--;
			return 1;
		}	
		p++;
		return 0;
	};
	int need_swap = get_bit();
	for(int i = 0; i < N; i++){
		int ans = 0;
		for(int j = 0; j < 8; j++){
			ans |= (get_bit() ^ need_swap) << j;
		}
		output(find(rd_hash[i].begin(), rd_hash[i].end(), ans) - rd_hash[i].begin());
	}
}

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