oj.uz

답안 #382681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382681 2021-03-28T02:43:02 Z jjang36524 앵무새 (IOI11_parrots) C++14
100 / 100
 264 ms 142728 KB 
    #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);
        }
     
    }
    #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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 141668 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 142060 KB Output is correct
2 Correct 156 ms 142068 KB Output is correct
3 Correct 169 ms 142072 KB Output is correct
4 Correct 165 ms 142072 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 142272 KB Output is correct
2 Correct 161 ms 141940 KB Output is correct
3 Correct 164 ms 142072 KB Output is correct
4 Correct 168 ms 141944 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 141932 KB Output is correct
2 Correct 165 ms 142728 KB Output is correct
3 Correct 174 ms 142076 KB Output is correct
4 Correct 196 ms 142252 KB Output is correct
5 Correct 196 ms 142232 KB Output is correct
6 Correct 202 ms 142232 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 142196 KB Output is correct - P = 5.000000
2 Correct 201 ms 142308 KB Output is correct - P = 5.000000
3 Correct 200 ms 142208 KB Output is correct - P = 5.000000
4 Correct 238 ms 142228 KB Output is correct - P = 5.000000
5 Correct 257 ms 142408 KB Output is correct - P = 5.000000
6 Correct 263 ms 142400 KB Output is correct - P = 5.000000
7 Correct 264 ms 142408 KB Output is correct - P = 5.000000