Submission #926502

#	Time	Username	Problem	Language	Result	Execution time	Memory
926502		hotboy2703	Parrots (IOI11_parrots)	C++14	100 / 100	24 ms	3232 KiB

encoder

#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"

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

const int maxn = 64;
const int maxv = 256;

int h[maxn][maxv];
int f[maxv], ans[maxn];
int ptr = 0;

void init(){
    memset(f, 0, sizeof(f));
    memset(ans, 0, sizeof(ans));
    ptr = 0;
    mt19937 rng(69420);
    for(int i = 0; i < 64; i++){
        for(int j = 0; j < 256; j++){
            h[i][j] = j;
        }
        shuffle(h[i], h[i] + maxv, rng);
    }
}

void send_bit(int x){
//    cout<<"SEND BIT "<<x<<' '<<ptr<<endl;
    if(x && ptr < maxv)send(ptr);
    else ptr++;
}

void encode(int N, int M[])
{
    init();
    int cnt1 = 0;
    for(int i = 0; i < N; i++)cnt1 += __builtin_popcount(h[i][M[i]]);
    int sw = 0;
    if(cnt1 < N*4){
        sw = 1;
        send_bit(0);
    }
    else send_bit(1);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 8; j++){
            send_bit((h[i][M[i]]>>j&1)^sw);
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"

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

const int maxn = 64;
const int maxv = 256;

int h[maxn][maxv];
int f[maxv], ans[maxn];
int ptr = 0;

void init(){
    memset(f, 0, sizeof(f));
    memset(ans, 0, sizeof(ans));
    ptr = 0;
    mt19937 rng(69420);
    for(int i = 0; i < 64; i++){
        for(int j = 0; j < 256; j++){
            h[i][j] = j;
        }
        shuffle(h[i], h[i] + maxv, rng);
    }
}


int get_bit(){
    if(ptr == maxv)return 1;
    else if(!f[ptr]){
        ptr++;
        return 0;
    }
    else {
        f[ptr]--;
        return 1;
    }
}


void decode(int N, int L, int X[])
{
    init();
    int sw = 0;
    for(int i = 0; i < L; i++)f[X[i]]++;
    if(!get_bit())sw = 1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 8; j++){
            ans[i] ^= (get_bit()^sw)<<j;
        }
        for(int j = 0; j < maxv; j++){
            if(h[i][j] == ans[i]){
                output(j);
                break;
            }
        }
    }
}

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