Submission #382681

#	Time	Username	Problem	Language	Result	Execution time	Memory
382681		jjang36524	Parrots (IOI11_parrots)	C++14	100 / 100	264 ms	142728 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];
      static int x;
        int i,j;
      if(x==0)
      {
        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]);
            }
        }
        x=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];
      static int x;
      sort(X,X+L);
        int i,j;
      if(x==0)
      {
        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]);
            }
        }
        x=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: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19