Submission #923367

#	Time	Username	Problem	Language	Result	Execution time	Memory
923367		bachhoangxuan	Parrots (IOI11_parrots)	C++17	98 / 100	7 ms	1560 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxa = 256;
#define pii pair<int,int>
#define fi first
#define se second

void encode(int N, int M[])
{
    pii Min={13*N,-1};
    for(int mask=0;mask<(1<<8);mask++){
        if(__builtin_popcount(mask)!=4) continue;
        int total=0;
        for(int i=0;i<N;i++){
            int d0=mask&M[i],d1=M[i]^d0;
            d0=__builtin_popcount(d0);
            d1=__builtin_popcount(d1);
            total+=d0+2*d1;
        }
        Min=min(Min,{total+4,mask<<1});
        Min=min(Min,{12*N-total+8,mask<<1|1});
    }
    int mask=Min.se>>1,rev=Min.se&1;
    for(int i=0;i<(1+rev)*4;i++) send(mask);
    vector<int> p0,p1;
    for(int i=0;i<8;i++){
        if(mask>>i&1) p0.push_back(i);
        else p1.push_back(i);
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<4;j++){
            int cnt=(M[i]>>p1[j]&1)<<1|(M[i]>>p0[j]&1);
            if(rev) cnt=3-cnt;
            for(int k=0;k<cnt;k++) send(i<<2|j);
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxa = 256;

int cnt[maxa];

void decode(int N, int L, int X[])
{
    for(int i=0;i<maxa;i++) cnt[i]=0;
    for(int i=0;i<L;i++) cnt[X[i]]++;
    int rev=0,mask=-1;
    for(int i=0;i<maxa;i++){
        if(cnt[i]>=4){
            mask=i;
            cnt[i]-=4;
        }
        if(cnt[i]>=4){
            rev=1;
            cnt[i]-=4;
        }
    }
    if(rev){
        for(int i=0;i<maxa;i++) cnt[i]=3-cnt[i];
    }
    vector<int> p0,p1;
    for(int i=0;i<8;i++){
        if(mask>>i&1) p0.push_back(i);
        else p1.push_back(i);
    }
    for(int i=0;i<N;i++){
        int cur=0;
        for(int j=0;j<4;j++){
            cur+=(cnt[i<<2|j]&1)<<p0[j];
            cur+=(cnt[i<<2|j]>>1)<<p1[j];
        }
        output(cur);
    }
}

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