Submission #382676

#	Time	Username	Problem	Language	Result	Execution time	Memory
382676		jjang36524	Parrots (IOI11_parrots)	C++14	17 / 100	2239 ms	142924 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include "decoder.h"
#include "decoderlib.h"
#include <stdlib.h>
#include <string.h>
#define DIGIT 65536
#include <algorithm>
using namespace std;
struct bigint
{
    int arr[50];
    bigint()
    {
        memset(arr,0,sizeof(arr));
    }
};
bigint plu(bigint a,bigint b)
{
    bigint ans;
    int i;
    for(i=0;i<49;i++)
    {
        int c=a.arr[i]+b.arr[i];
        ans.arr[i+1]+=c>>16;
        ans.arr[i]+=c&(65535);
    }
    return ans;
}
bigint minu(bigint a,bigint b)
{
    bigint ans;
    int i;
    for(i=0;i<50;i++)
    {
        while(a.arr[i]<b.arr[i])
        {
            a.arr[i]+=DIGIT;
            a.arr[i+1]--;
        }
        ans.arr[i]=a.arr[i]-b.arr[i];
    }
    return ans;
}
bool cmp(bigint a,bigint b)
{
    bigint ans;
    int i;
    for(i=49;i>=0;i--)
    {
        if(a.arr[i]!=b.arr[i])
        {
            return a.arr[i]>b.arr[i];
        }
    }
    return 1;
}

void encode(int N, int M[])
{
    static bigint comb[600][600];
    int i,j;
    for(i=0;i<600;i++)
    {
        comb[i][0].arr[0]=1;
    }
    for(i=1;i<600;i++)
    {
        for(j=1;j<=i;j++)
        {
            comb[i][j]=plu(comb[i-1][j],comb[i-1][j-1]);
        }
    }
    bigint mul=comb[0][0];
    bigint an;
    for(i=0;i<N;i++)
    {
        for(j=0;j<M[i];j++)
        {
            an=plu(an,mul);
        }
        for(j=0;j<8;j++)
        {
            mul=plu(mul,mul);
        }
    }
    int K=5*N;
    int c=0;
    for(i=0;i<K;i++)
    {
        while(c<255&&cmp(an,comb[256-c+(K-i-1)-1][K-i-1]))
        {
            an=minu(an,comb[256-c+(K-i-1)-1][K-i-1]);
            c++;

        }
        send(c);
    }

}

decoder

#include "encoder.h"
#include "encoderlib.h"
#include "decoder.h"
#include "decoderlib.h"
#include <stdlib.h>
#include <string.h>
#define DIGIT 65536
#include <algorithm>
using namespace std;
struct bigint
{
    int arr[50];
    bigint()
    {
        memset(arr,0,sizeof(arr));
    }
};
bigint pluu(bigint a,bigint b)
{
    bigint ans;
    int i;
    for(i=0;i<49;i++)
    {
        int c=a.arr[i]+b.arr[i];
        ans.arr[i+1]+=c>>16;
        ans.arr[i]+=c&(65535);
    }
    return ans;
}
bigint minuu(bigint a,bigint b)
{
    bigint ans;
    int i;
    for(i=0;i<50;i++)
    {
        while(a.arr[i]<b.arr[i])
        {
            a.arr[i]+=DIGIT;
            a.arr[i+1]--;
        }
        ans.arr[i]=a.arr[i]-b.arr[i];
    }
    return ans;
}
bool cmpu(bigint a,bigint b)
{
    bigint ans;
    int i;
    for(i=49;i>=0;i--)
    {
        if(a.arr[i]!=b.arr[i])
        {
            return a.arr[i]>b.arr[i];
        }
    }
    return 1;
}

void decode(int N, int L, int X[])
{
    static bigint comb[600][600];
    sort(X,X+L);
    int i,j;
    for(i=0;i<600;i++)
    {
        comb[i][0].arr[0]=1;
    }
    for(i=1;i<600;i++)
    {
        for(j=1;j<=i;j++)
        {
            comb[i][j]=pluu(comb[i-1][j],comb[i-1][j-1]);
        }
    }
    bigint an;
    bigint mul[100];
    mul[0].arr[0]=1;
    for(i=1;i<N;i++)
    {
        mul[i]=mul[i-1];
        int j;
        for(j=0;j<8;j++)
            mul[i]=pluu(mul[i],mul[i]);
    }
    int c=0;
    for(i=0;i<L;i++)
    {
        while(c<X[i])
        {
            an=pluu(an,comb[256-c+(L-i-1)-1][L-i-1]);
            c++;
        }
    }
    int ans[100];
    memset(ans,0,sizeof(ans));
    for(i=N-1;i>=0;i--)
    {
        int cur=0;
        while(cmpu(an,mul[i]))
        {
            cur++;
            an=minuu(an,mul[i]);
        }
        ans[i]=cur;
    }
    for(i=0;i<N;i++)
    {
        output(ans[i]);
    }
}

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