Submission #924638

#	Time	Username	Problem	Language	Result	Execution time	Memory
924638		huutuan	Parrots (IOI11_parrots)	C++14	100 / 100	1165 ms	56040 KiB

encoder

#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';
}

decoder

#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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19