Submission #1146136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146136		SmuggingSpun	Parrots (IOI11_parrots)	C++20	81 / 100	11 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;
	vector<vector<int>>rd_hash(N, vector<int>(256));
	for(int i = 0; i < N; i++){
		rng.seed((i << 8) + i * i * i / 3 + 4);
		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);
		}
	}
}

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;
	vector<vector<int>>rd_hash(N, vector<int>(256));
	for(int i = 0; i < N; i++){
		rng.seed((i << 8) + i * i * i / 3 + 4);
		iota(rd_hash[i].begin(), rd_hash[i].end(), 0);
		shuffle(rd_hash[i].begin(), rd_hash[i].end(), rng);
	}
	sort(X, X + L);
	int need_swap = int(X[0] == 0);
	vector<bool>bit(N << 3, need_swap == 1);
	for(int j = need_swap, p = 0; j < L; j++, p++){
		bit[p += X[j] - (j == 0 ? 0 : X[j - 1])] = bool(need_swap == 0);
	}
	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(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