oj.uz

답안 #924638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924638 2024-02-09T10:47:34 Z huutuan 앵무새 (IOI11_parrots) C++14
100 / 100
 1165 ms 56040 KB 
#ifndef BIGNUM_H_
#define BIGNUM_H_

#include <bits/stdc++.h>

using namespace std;

struct Bignum{
   vector<int> value;
   void norm(){
      while (value.size() && value.back()==0) value.pop_back();
      if (value.empty()) value.push_back(0);
   }
   Bignum(int x=0){
      while (x){
         value.push_back(x&255);
         x>>=8;
      }
   }
   Bignum operator+(Bignum b){
      Bignum a=*this, c;
      while (a.value.size()<b.value.size()) a.value.push_back(0);
      while (b.value.size()<a.value.size()) b.value.push_back(0);
      c.value.resize(a.value.size());
      int carry=0;
      for (int i=0; i<(int)c.value.size(); ++i){
         int sum=a.value[i]+b.value[i]+carry;
         c.value[i]=sum&255;
         carry=sum>>8;
      }
      if (carry) c.value.push_back(carry);
      return c;
   }
   bool operator<(Bignum b){
      Bignum a=*this;
      if (a.value.size()<b.value.size()) return 1;
      if (a.value.size()>b.value.size()) return 0;
      for (int i=(int)a.value.size()-1; i>=0; --i){
         if (a.value[i]!=b.value[i]){
            return a.value[i]<b.value[i];
         }
      }
      return 0;
   }
   Bignum operator-(Bignum b){
      Bignum a=*this, c;
      assert(!(a<b));
      while (b.value.size()<a.value.size()) b.value.push_back(0);
      c.value.resize(a.value.size());
      int carry=0;
      for (int i=0; i<(int)a.value.size(); ++i){
         int diff=a.value[i]-b.value[i]-carry;
         if (diff<0){
            diff+=256;
            carry=1;
         }else carry=0;
         c.value[i]=diff;
      }
      c.norm();
      return c;
   }
};

#endif
#include "encoder.h"
#include "encoderlib.h"
#include "decoder.h"
#include "decoderlib.h"

#ifdef sus
#include "bignum.h"
#endif

#include <bits/stdc++.h>

using namespace std;

Bignum f[321][257], pf[321][257];

void precalc(int mxlen){
   for (int val=0; val<256; ++val) f[0][val]=1, pf[0][val]=256-val;
   for (int len=1; len<=mxlen; ++len){
      for (int val=0; val<256; ++val){
         f[len][val]=pf[len-1][val];
      }
      pf[len][255]=f[len][255];
      for (int val=254; val>=0; --val) pf[len][val]=f[len][val]+pf[len][val+1];
   }
}

void encode(int n, int a[])
{
   int mxlen=n*5;
   precalc(mxlen);
   Bignum cur;
   for (int i=0; i<n; ++i) cur.value.push_back(a[i]);
   cur.norm();
   int lst=0;
   for (int i=1; i<=mxlen; ++i){
      for (int val=lst; val<256; ++val){
         if (cur<f[mxlen-i][val]){
            send(val);
            cerr << val << ' ';
            lst=val;
            break;
         }
         cur=cur-f[mxlen-i][val];
      }
   }
   cerr << '\n';
}

#ifndef BIGNUM_H_
#define BIGNUM_H_

#include <bits/stdc++.h>

using namespace std;

struct Bignum{
   vector<int> value;
   void norm(){
      while (value.size() && value.back()==0) value.pop_back();
      if (value.empty()) value.push_back(0);
   }
   Bignum(int x=0){
      while (x){
         value.push_back(x&255);
         x>>=8;
      }
   }
   Bignum operator+(Bignum b){
      Bignum a=*this, c;
      while (a.value.size()<b.value.size()) a.value.push_back(0);
      while (b.value.size()<a.value.size()) b.value.push_back(0);
      c.value.resize(a.value.size());
      int carry=0;
      for (int i=0; i<(int)c.value.size(); ++i){
         int sum=a.value[i]+b.value[i]+carry;
         c.value[i]=sum&255;
         carry=sum>>8;
      }
      if (carry) c.value.push_back(carry);
      return c;
   }
   bool operator<(Bignum b){
      Bignum a=*this;
      if (a.value.size()<b.value.size()) return 1;
      if (a.value.size()>b.value.size()) return 0;
      for (int i=(int)a.value.size()-1; i>=0; --i){
         if (a.value[i]!=b.value[i]){
            return a.value[i]<b.value[i];
         }
      }
      return 0;
   }
   Bignum operator-(Bignum b){
      Bignum a=*this, c;
      assert(!(a<b));
      while (b.value.size()<a.value.size()) b.value.push_back(0);
      c.value.resize(a.value.size());
      int carry=0;
      for (int i=0; i<(int)a.value.size(); ++i){
         int diff=a.value[i]-b.value[i]-carry;
         if (diff<0){
            diff+=256;
            carry=1;
         }else carry=0;
         c.value[i]=diff;
      }
      c.norm();
      return c;
   }
};

#endif
#include "decoder.h"
#include "decoderlib.h"

#ifdef sus
#include "bignum.h"
#endif

#include <bits/stdc++.h>

using namespace std;

Bignum f[321][257], pf[321][257];

void precalc(int mxlen){
   for (int val=0; val<256; ++val) f[0][val]=1, pf[0][val]=256-val;
   for (int len=1; len<=mxlen; ++len){
      for (int val=0; val<256; ++val){
         f[len][val]=pf[len-1][val];
      }
      pf[len][255]=f[len][255];
      for (int val=254; val>=0; --val) pf[len][val]=f[len][val]+pf[len][val+1];
   }
}

void decode(int n, int m, int a[])
{
   precalc(m);
   sort(a, a+m);
   Bignum cur;
   for (int i=0; i<m; ++i){
      for (int val=i?a[i-1]:0; val<a[i]; ++val) cur=cur+f[m-i-1][val];
   }
   cur.value.resize(n);
   for (int i:cur.value) output(i);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 12544 KB Output is correct
2 Correct 128 ms 14132 KB Output is correct
3 Correct 184 ms 16100 KB Output is correct
4 Correct 190 ms 16584 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 12680 KB Output is correct
2 Correct 131 ms 14036 KB Output is correct
3 Correct 178 ms 16112 KB Output is correct
4 Correct 199 ms 16656 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 12672 KB Output is correct
2 Correct 191 ms 16668 KB Output is correct
3 Correct 246 ms 19064 KB Output is correct
4 Correct 392 ms 26120 KB Output is correct
5 Correct 430 ms 26776 KB Output is correct
6 Correct 424 ms 27308 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 16584 KB Output is correct
2 Correct 442 ms 27336 KB Output is correct
3 Correct 451 ms 27872 KB Output is correct
4 Correct 858 ms 42636 KB Output is correct
5 Correct 1090 ms 52524 KB Output is correct
6 Correct 1128 ms 55272 KB Output is correct
7 Correct 1165 ms 56040 KB Output is correct