Submission #7717

#	Time	Username	Problem	Language	Result	Execution time	Memory
7717		baneling100	Parrots (IOI11_parrots)	C++98	100 / 100	11 ms	2432 KiB

encoder

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

static int A[21];
static long long C[41][41];

long long static H(int X, int Y) {

    return C[X+Y-1][X];
}

void static MakeSequence(long long Num, int K) {

    int i, j;
    long long Temp;

    for(i=1 ; i<=K ; i++)
        for(j=A[i-1] ; j<=16 ; j++) {
            Temp=H(K-i,17-j);
            if(Num<=Temp || !Temp) {
                A[i]=j;
                break;
            }
            else
                Num-=Temp;
        }
}

void encode(int N, int M[]) {

    int i, j;
    long long Num;

    for(i=1 ; i<=40 ; i++) {
        C[i][0]=C[i][i]=1;
        for(j=1 ; j<=i-1 ; j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    for(i=3 ; i<N ; i+=4) {
        Num=(long long)M[i-3]+(long long)256*M[i-2]+(long long)256*256*M[i-1]+(long long)256*256*256*M[i];
        MakeSequence(Num,20);
        for(j=1 ; j<=20 ; j++)
            if(A[j]!=16)
                send((i/4)+(A[j]<<4));
    }
    if(N%4==1) {
        Num=(long long)M[N-1];
        MakeSequence(Num,5);
        for(j=1 ; j<=5 ; j++)
            if(A[j]!=16)
                send(((N-1)/4)+(A[j]<<4));
    }
    else if(N%4==2) {
        Num=(long long)M[N-2]+(long long)256*M[N-1];
        MakeSequence(Num,10);
        for(j=1 ; j<=10 ; j++)
            if(A[j]!=16)
                send(((N-1)/4)+(A[j]<<4));
    }
    else if(N%4==3) {
        Num=(long long)M[N-3]+(long long)256*M[N-2]+(long long)256*256*M[N-1];
        MakeSequence(Num,15);
        for(j=1 ; j<=15 ; j++)
            if(A[j]!=16)
                send(((N-1)/4)+(A[j]<<4));
    }
}

decoder

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

using namespace std;

static int M, Group[16][21], Cnt[16], Ans[65], Len;
static long long C[41][41];

long long static H(int X, int Y) {

    return C[X+Y-1][X];
}

long long static RemoveSequence(int X, int Y) {

    int i, j;
    long long Num=0;

    for(i=1 ; i<=Y ; i++)
        for(j=Group[X][i-1] ; j<Group[X][i] ; j++)
            Num+=H(Y-i,17-j);
    if(Num)
        Num++;
    return Num;
}

void decode(int N, int L, int X[]) {

    int i, j, Temp1, Temp2;
    long long Num;

    for(i=0 ; i<=15 ; i++)
        Cnt[i]=0;
    Len=0;
    for(i=1 ; i<=40 ; i++) {
        C[i][0]=C[i][i]=1;
        for(j=1 ; j<=i-1 ; j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    M=N/4;
    for(i=0 ; i<L ; i++) {
        Temp2=(X[i]>>4);
        Temp1=X[i]-(Temp2<<4);
        Group[Temp1][++Cnt[Temp1]]=Temp2;
    }
    for(i=0 ; i<M ; i++) {
        for(j=Cnt[i]+1 ; j<=20 ; j++)
            Group[i][j]=16;
        sort(Group[i]+1,Group[i]+21);
        Num=RemoveSequence(i,20);
        for(j=1 ; j<=4 ; j++) {
            Ans[++Len]=Num%256;
            Num/=256;
        }
    }
    if(N%4==1) {
        for(j=Cnt[M]+1 ; j<=5 ; j++)
            Group[M][j]=16;
        sort(Group[M]+1,Group[M]+6);
        Num=RemoveSequence(M,5);
        Ans[++Len]=Num%256;
        Num/=256;
    }
    else if(N%4==2) {
        for(j=Cnt[M]+1 ; j<=10 ; j++)
            Group[M][j]=16;
        sort(Group[M]+1,Group[M]+11);
        Num=RemoveSequence(M,10);
        for(j=1 ; j<=2 ; j++) {
            Ans[++Len]=Num%256;
            Num/=256;
        }
    }
    else if(N%4==3) {
        for(j=Cnt[M]+1 ; j<=15 ; j++)
            Group[M][j]=16;
        sort(Group[M]+1,Group[M]+16);
        Num=RemoveSequence(M,15);
        for(j=1 ; j<=3 ; j++) {
            Ans[++Len]=Num%256;
            Num/=256;
        }
    }
    for(i=1 ; i<=N ; i++)
        output(Ans[i]);
}

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