Submission #1141027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141027		hyl_kibou	Parrots (IOI11_parrots)	C++17	98 / 100	5 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#include <vector>

void encode(int N, int M[])
{
    int nor[N*4+7];
    int inv[N*4+7];

    int a;
    int sum1 = 0;
    int sum2 = 0;
    int sum3 = 0;


    for(int i = 0; i<N; ++i){
        int a = M[i];
        for(int j = 0; j<4; ++j){
           nor[i*4+j] = a%4;
           sum1 += a%4;
           inv[i*4+j] = 3-a%4;
           sum2 += 3-a%4;

           if(j%2){
                sum3 += a%4;
                //printf("%d %d\n", sum3);
           }
           else{
                sum3 += 3-a%4;
                //printf("%d %d\n", sum3);
           }
            //printf("%d %d %dY0\n", i, j, sum3);

           a/=2;
           a/=2;
        }
    }

    /*
    for(int i = 0; i<N*4; ++i){

        printf("%d ", nor[i]);

    }
    printf("\n");

    for(int i = 0; i<N*4; ++i){

        printf("%d ", inv[i]);

    }
    printf("\n");

    for(int i = 0; i<N*4; ++i){

        if(i%2){
            printf("%d ", nor[i]);
        }
        else{
            printf("%d ", inv[i]);
        }

    }
    printf("\n");
    //*/


    //printf("%d %d %d %d\n", sum1, sum2, sum3, sum1+sum2-sum3);


    int extra = 256;
    int curr = sum1-4;


    if(curr>sum2){
        extra = 255;
        curr = sum2;
    }
    if(curr>sum3){
        extra = 254;
        curr = sum3;
    }
    if(curr>sum1+sum2-sum3){
        extra = 253;
    }

    for(int i = 0; i<N*4; ++i){
        if(extra == 256){
            curr = nor[i];
        }
        if(extra == 255){
            curr = inv[i];
        }
        if(extra == 254){
            if(i%2){
                curr = nor[i];
            }
            else{
                curr = inv[i];
            }
        }
        if(extra == 253){
            if(i%2){
                curr = inv[i];
            }
            else{
                curr = nor[i];
            }
        }

        for(int j = 0; j<curr; ++j){
            //printf("%d_", i);
            send(i);
        }

    }

    for(int i = 0; i<4; ++i){
        if(extra!=256){
            send(extra);
        }
    }

    //send();
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>

//int exo[] = {1, 2, 4, 8, 16, 32, 64, 128};

void decode(int N, int L, int X[])
{
  std::sort(X, X+L);

  int arr[256] = {};

  for(int i = 0; i<L; ++i){
    ++arr[X[i]];
  }

  if(arr[255]>=4){
    arr[255]-=4;

    for(int i = 0; i<N*4; i+=4){
        int sum = 0;
        sum+=3-arr[i];
        sum+=(3-arr[i+1])*4;
        sum+=(3-arr[i+2])*16;
        sum+=(3-arr[i+3])*64;
        output(sum);
    }
    return;
  }
  if(arr[253]>=4){
    arr[253]-=4;

    for(int i = 0; i<N*4; i+=4){
        int sum = 0;

        sum+=arr[i];
        sum+=(3-arr[i+1])*4;
        sum+=(arr[i+2])*16;
        sum+=(3-arr[i+3])*64;
        output(sum);
    }
    return;
  }

  if(arr[254]>=4){
    arr[254]-=4;

    for(int i = 0; i<N*4; i+=4){
        int sum = 0;

        sum+=3-arr[i];
        sum+=(arr[i+1])*4;
        sum+=(3-arr[i+2])*16;
        sum+=(arr[i+3])*64;
        //printf("%d ", sum);
        output(sum);
    }
    return;
  }

    for(int i = 0; i<N*4; i+=4){
        int sum = 0;
        sum+=arr[i];
        sum+=(arr[i+1])*4;
        sum+=(arr[i+2])*16;
        sum+=(arr[i+3])*64;
        output(sum);
    }

  //output();
}

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