Submission #20251

#	Time	Username	Problem	Language	Result	Execution time	Memory
20251		tkxkd7223	Parrots (IOI11_parrots)	C++98	0 / 100	10 ms	2512 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#define LL long long

static int k[40];
static int a[5];
static int sending;
static LL H[25][25];
static LL C[55][55];
static LL cnt=0;

void hh(){
    int i, j;
    for(i=1 ; i<=50 ; i++){
        C[1][1]=1;
        C[i][0]=C[i][i]=1;
        for(j=1 ; j<=50 ; j++){
            if(i==1 && j==1)continue;
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
        C[i][0]=C[i][i]=1;
    }
    for(i=1 ; i<=20 ; i++){
        for(j=1 ; j<=20 ; j++){
            H[i][j]=C[i+j-1][j];
        }
    }
}

void find1(){
    int i, j;
    int t=0;
    LL gap=0;
    for(i=19, j=17 ; i>=0 && j>=0 ; i--){
        while(gap+H[j][i]<=cnt){
            gap+=H[j][i];
            t++;
            j--;
            if(j<=1)break;
        }
        k[20-i]=t;
    }
}
void encode(int N, int M[]) {
    int i, p, j;
    int g=0;
    hh();
    for(i=0; i<N; i+=4) {
        g=i/4;
        p=cnt=0;
        cnt=(LL)M[i]+(LL)M[i+1]*256+(LL)M[i+2]*256*256+(LL)M[i+3]*256*256*256;
        find1();
        for(j=3 ; j>=0 ; j--){
            a[j]=g%2;
            g/=2;
        }
        int temp=a[0]*2*2*2+a[1]*2*2+a[2]*2+a[3];
        for(j=1 ; j<=20 ; j++){
            if(k[j]!=16)send(temp*16+k[j]);
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
#include <string.h>
#include <stdio.h>
#define LL long long

struct data{
    int x, y;
    bool operator <(const data&r)const{
        if(x!=r.x)return x<r.x;
        return y<r.y;
    }
};

static data indexi[50];
long long p;
static LL H[25][25];
static LL C[45][25];
static long long ap[25];

void hc(){
    int i, j;
    for(i=1 ; i<=40 ; i++){
        C[1][1]=1;
        C[i][0]=C[i][i]=1;
        for(j=1 ; j<=20 ; j++){
            if(i==1 && j==1)continue;
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
        C[i][0]=C[i][i]=1;
    }
    for(i=1 ; i<=20 ; i++){
        for(j=1 ; j<=20 ; j++){
            H[i][j]=C[i+j-1][j];
        }
    }
}

void check(){
    int i, j;
    p=0;
    for(i=1 ; i<=20 ; i++){
        if(ap[i]!=ap[i-1]){
            p+=(LL)H[17-ap[i]][20-i]*(ap[i]-ap[i-1]);
        }
    }
    for(int i=0 ; i<=3 ; i++){
        printf("%lld ", p%256);
        output(p%256);
        p/=256;
    }
    printf("\n");
}
void check1(){
    int i, j;
    p=0;
    for(i=1 ; i<=15 ; i++){
        if(ap[i]!=ap[i-1]){
            p+=H[17-ap[i]][15-i]*(ap[i]-ap[i-1]);
        }
    }
    for(int i=0 ; i<=2 ; i++){
        output(p%256);
        p;
    }
}
void check2(){
    int i, j;
    p=0;
    for(i=1 ; i<=10 ; i++){
        if(ap[i]!=ap[i-1]){
            p+=H[17-ap[i]][10-i]*(ap[i]-ap[i-1]);
        }
    }
    for(int i=0 ; i<=1 ; i++){
        output(p%256);
        p;
    }
}
void check3(){
    int i, j;
    p=0;
    for(i=1 ; i<=5 ; i++){
        if(ap[i]!=ap[i-1]){
            p+=H[17-ap[i]][5-i]*(ap[i]-ap[i-1]);
        }
    }
    for(int i=0 ; i<=0 ; i++){
        output(p%256);
        p;
    }
}

void decode(int N, int L, int X[]){
    int i, b, j;
    hc();
    for(i=0; i<L; i++) {
        b = X[i];
        indexi[i].y=b%16;
        b/=16;
        indexi[i].x=b%16;
    }
    std::sort(indexi, indexi+L);
    int cnt=0;
    for(i=0 ; i<L ; i++){
        if(indexi[i].x!=indexi[i+1].x){
            if(N/4>=indexi[i].x){
                for(int j=cnt+1; j<=20 ; j++){
                    ap[j]=16;
                }
                check();
            }
            else if(N%4==1){
                for(int j=cnt+1; j<=15 ; j++){
                    ap[j]=16;
                }
                check1();
            }
            else if(N%4==2){
                for(int j=cnt+1; j<=10 ; j++){
                    ap[j]=16;
                }
                check2();
            }
            else{
                for(int j=cnt+1; j<=5 ; j++){
                    ap[j]=16;
                }
                check3();
            }
            cnt=0;
            memset(ap, 0, sizeof(ap));
        }
        else ap[++cnt]=indexi[i].y;
    }
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:45:12: warning: variable 'p' set but not used [-Wunused-but-set-variable]
     int i, p, j;
            ^
encoder.cpp: At global scope:
encoder.cpp:7:12: warning: 'sending' defined but not used [-Wunused-variable]
 static int sending;
            ^~~~~~~

decoder.cpp: In function 'void check()':
decoder.cpp:41:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
decoder.cpp: In function 'void check1()':
decoder.cpp:65:10: warning: statement has no effect [-Wunused-value]
         p;
          ^
decoder.cpp:56:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
decoder.cpp: In function 'void check2()':
decoder.cpp:78:10: warning: statement has no effect [-Wunused-value]
         p;
          ^
decoder.cpp:69:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
decoder.cpp: In function 'void check3()':
decoder.cpp:91:10: warning: statement has no effect [-Wunused-value]
         p;
          ^
decoder.cpp:82:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:96:15: warning: unused variable 'j' [-Wunused-variable]
     int i, b, j;
               ^
decoder.cpp: In function 'void hc()':
decoder.cpp:31:24: warning: iteration 24 invokes undefined behavior [-Waggressive-loop-optimizations]
         C[i][0]=C[i][i]=1;
                 ~~~~~~~^~
decoder.cpp:24:16: note: within this loop
     for(i=1 ; i<=40 ; i++){
               ~^~~~

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