oj.uz

Submission #7717

# Submission time Handle Problem Language Result Execution time Memory
7717 2014-08-16T07:44:39 Z baneling100 Parrots (IOI11_parrots) C++
100 / 100
 11 ms 2432 KB 
#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));
    }
}

#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 752 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1592 KB Output is correct
2 Correct 8 ms 1592 KB Output is correct
3 Correct 6 ms 1744 KB Output is correct
4 Correct 5 ms 1928 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2248 KB Output is correct
2 Correct 5 ms 2248 KB Output is correct
3 Correct 6 ms 2248 KB Output is correct
4 Correct 5 ms 2248 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2248 KB Output is correct
2 Correct 5 ms 2248 KB Output is correct
3 Correct 6 ms 2352 KB Output is correct
4 Correct 7 ms 2352 KB Output is correct
5 Correct 7 ms 2352 KB Output is correct
6 Correct 7 ms 2352 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2352 KB Output is correct - P = 5.000000
2 Correct 7 ms 2352 KB Output is correct - P = 5.000000
3 Correct 7 ms 2352 KB Output is correct - P = 5.000000
4 Correct 9 ms 2384 KB Output is correct - P = 5.000000
5 Correct 11 ms 2432 KB Output is correct - P = 5.000000
6 Correct 11 ms 2432 KB Output is correct - P = 5.000000
7 Correct 11 ms 2432 KB Output is correct - P = 5.000000