Submission #235626

#	Time	Username	Problem	Language	Result	Execution time	Memory
235626		DavidDamian	Parrots (IOI11_parrots)	C++11	96 / 100	17 ms	1792 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
///Represent the numbers as a binary string
///Send the numbers in pairs of binary digits
void encode(int N, int M[])
{
    if(N<=16){
        int idx=0;
        for(int i=0;i<N;i++){
            for(int bit=0;bit<8;bit++){
                if(M[i]&(1<<bit))
                    send(idx+bit);
            }
            idx+=8;
        }
    }
    else{
        vector<int> bits(8*N,0);
        int idx=0;
        int sum=0;
        for(int i=0;i<N;i++){
            for(int bit=0;bit<8;bit++){
                if(M[i]&(1<<bit))
                    bits[idx+bit]=1,sum++;
            }
            idx+=8;
        }
        int scheme=(sum<=(N/2))? 1 : 0;
        for(int i=0;i<8*N;i+=2){
            int cnt=0;
            cnt+=bits[i];
            cnt+=(bits[i+1]<<1);
            if(scheme==0) cnt=3-cnt;
            while(cnt--)
                send(i/2);
        }
        if(scheme==0){
            send(255);
            send(255);
            send(255);
            send(255);
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
///Represent the numbers as a binary string
///Send the numbers in pairs of binary digits
void decode(int N, int L, int X[])
{
    if(N<=16){
        vector<int> binary(8*N,0);
        sort(X,X+L);
        for(int i=0;i<L;i++){
            binary[X[i]]=1;
        }
        for(int i=0;i<8*N;i+=8){
            int number=0;
            for(int bit=0;bit<8;bit++){
                if(binary[i+bit]) number+=(1<<bit);
            }
            output(number);
        }
    }
    else{
        vector<int> bucket(256,0);
        vector<int> bits(8*N,0);
        for(int i=0;i<L;i++){
            bucket[ X[i] ]++;
        }
        int scheme=(bucket[255]>=4)? 0 : 1;
        for(int i=0;i<4*N;i++){
            int cnt=bucket[i];
            if(i==255 && scheme==0) cnt-=4;
            if(scheme==0) cnt=3-cnt;
            if(cnt==1)
                bits[2*i]=1;
            else if(cnt==2)
                bits[2*i+1]=1;
            else if(cnt==3)
                bits[2*i]=bits[2*i+1]=1;
        }
        int idx=0;
        for(int i=0;i<N;i++){
            int number=0;
            for(int bit=0;bit<8;bit++){
                if(bits[idx+bit]) number+=(1<<bit);
            }
            idx+=8;
            output(number);
        }
    }
}

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