Submission #234387

#	Time	Username	Problem	Language	Result	Execution time	Memory
234387		Nodir_Bobiev	Parrots (IOI11_parrots)	C++14	81 / 100	2085 ms	2048 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <algorithm>

int* get(int x){
    int *cnt = new int[10];
    for( int j = 0; j < 10; j ++ ) cnt[j] = 0;
    if( __builtin_popcount(x) <= 3 ){
        cnt[7] += 2;
        for( int j = 0; j < 8; j ++ ){
            if( (x&(1<<j)) )
                cnt[j] ++;
        }
    }else{
        cnt[0] += 2;
        for( int j = 0; j < 8; j ++ ){
            if( !(x&(1<<j)) )
                cnt[j]++;
        }
    }
    return cnt;
}
void encode(int N, int M[])
{
    int len = std::min(32,N);
    for(int i=0; i<len; i++){
        int *qnt = get(M[i]);
        for( int j = 0; j < 8; j ++ ){
            while( qnt[j] -- ){
                send((i<<3)+j);
            }
        }
    }
    for(int i=len; i<N; i++){
        int *qnt = get(M[i]);
        for( int j = 0; j < 8; j ++ ){
            qnt[j] *= 4;
            while(qnt[j]--){
                send(((i-len)<<3)+j);
            }
        }
        delete qnt;
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
int* get(int x){
    int *cnt = new int[10];
    for( int j = 0; j < 10; j ++ ) cnt[j] = 0;
    if( __builtin_popcount(x) <= 3 ){
        cnt[7] += 2;
        for( int j = 0; j < 8; j ++ ){
            if( (x&(1<<j)) )
                cnt[j] ++;
        }
    }else{
        cnt[0] += 2;
        for( int j = 0; j < 8; j ++ ){
            if( !(x&(1<<j)) )
                cnt[j]++;
        }
    }
    return cnt;
}
void decode(int N, int L, int X[])
{
    int cnt[N][10]={};
    for( int i = 0; i < L; i ++ ){
        int x = X[i];
        int y = x % 8;
        int z = (x / 8);
        cnt[z][y] ++;
    }
    int ans[N] = {}, len = std::min(32, N);
    for( int i = 0; i < len; i ++ ){
        if( i+len < N ){
            bool ff = false;
            for( int x = 0; x <= 255; x ++ ){
                if( ff )break;
                for( int y = 0; y <= 255; y ++ ){
                    int *qnt1 = get( x ), *qnt2 = get(y), qnt[10] = {};
                    for( int j = 0; j < 8; j ++ ){
                        qnt[j] = qnt1[j] + 4*qnt2[j];
                    }
                    ff = true;
                    for( int j = 0; j < 8; j ++ ){
                        if( qnt[j] != cnt[i][j] )
                            ff = false;
                    }
                    delete qnt1;
                    delete qnt2;
                    if( ff ){
                        ans[i] = x;
                        ans[i+len] = y;
                        break;
                    }
                }
            }
        }
        else{
            for( int x = 0; x <= 255; x ++ ){
                int *qnt = get(x);
                bool ff = true;
                for( int j = 0; j < 8; j ++ ){
                    if( cnt[i][j] != qnt[j] )
                        ff = false;
                }
                delete qnt;
                if( ff ){
                    ans[i] = x;
                    break;
                }
            }
        }
    }
    for( int i = 0; i < N; i ++ ){
        output(ans[i]);
    }
}

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