Submission #1023022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023022		socpite	Parrots (IOI11_parrots)	C++17	100 / 100	18 ms	1708 KiB

encoder

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

namespace{
int rdhash[64][256];

int ptr = 0;
}

void sendbit(int x){
	if(x)send(ptr);
	else ptr++;
}

void encode(int N, int M[])
{
	mt19937 rng(123);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 256; j++)rdhash[i][j] = j;
		shuffle(rdhash[i], rdhash[i] + 256, rng);
	}
	int cnt = 0;
	for(int i = 0; i < N; i++){
		int tval = rdhash[i][M[i]];
		cnt += __builtin_popcount(tval);
	}
	ptr = 0;
	int swapped = cnt < 4*N;
	sendbit(swapped);
	for(int i = 0; i < N; i++){
		int tval = rdhash[i][M[i]];
		for(int j = 0; j < 8; j++)sendbit(((tval>>j)&1)^swapped);
	}
	
}

decoder

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

namespace{

int rdhash[64][256];
int cnt[1000];

int ptr = 0;
}

int getbit(){
	if(cnt[ptr]){
		cnt[ptr]--;
		return 1;
	}
	ptr++;
	return 0;
}

void decode(int N, int L, int X[])
{
	mt19937 rng(123);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 256; j++)rdhash[i][j] = j;
		shuffle(rdhash[i], rdhash[i] + 256, rng);
	}
	ptr = 0;
	memset(cnt, 0, sizeof(cnt));
	for(int i = 0; i < L; i++)cnt[X[i]]++;

	int swapped = getbit();
	for(int i = 0; i < N; i++){
		int val = 0;
		for(int j = 0; j < 8; j++){
			val |= (getbit()^swapped)<<j;
		}
		output(find(rdhash[i], rdhash[i] + 256, val) - rdhash[i]);
	}
}

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