Submission #1047825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047825		anton	Parrots (IOI11_parrots)	C++17	100 / 100	1990 ms	127628 KiB

encoder

  #include "encoder.h"
  #include "encoderlib.h"

  #include<bits/stdc++.h>
  using namespace std;

  const int MOD = (1<<8);
  const int LEN = 90;
  struct lInt{
      vector<int> v;
      lInt(){
          v= vector<int>(LEN);
      };
      lInt(long long l){
          v= vector<int>(LEN);
          int i=0;
          while(l>0){
              v[i] = l%MOD;
              l/=MOD;
              i++;
          }
      }
      lInt operator+(const lInt& rh){
          lInt res;
          int carry = 0;
          for(int i = 0; i<LEN; i++){
              int r = v[i] + rh.v[i] + carry;
              res.v[i] = r%MOD;
              carry = r/MOD;
          }
          assert(carry == 0);
          return res;
      }

      bool operator<(const lInt& rh)const{
        for(int i = LEN-1; i>=0; i--){
          if(v[i]!=rh.v[i]){
            return v[i]<rh.v[i];
          }
        }
        return false; 
      }

      long long to_ll(){
          long long res= 0;
          for(int i = LEN-1; i>=0; i--){
              res *= MOD;
              res += v[i];
          }
          return res;
      }
  };

  const int P = 5;
  const int K = (1<<8);
  int N;
  vector<vector<lInt>> dp;

  void calc_dp(){
    for(int i = 0; i<K; i++){
      dp[P*N-1][i].v[0] = 1;
    }

    for(int step = P*N -2; step>=0; step--){
      lInt pref;
      for(int i = K-1; i>=0; i--){
        pref = pref + dp[step+1][i];
        dp[step][i] = pref;
      }
    }
  }
  void encode(int n, int M[])
  {
    N = n;
    dp = vector<vector<lInt>>(P*N + 1, vector<lInt>((1<<8)));
    
    calc_dp();
    lInt requested;
    for(int i = 0; i<N; i++){
      requested.v[N-i-1] = M[i];
    }
    //cout<<requested.to_ll()<<endl;

    int cur_pos =0;
    vector<int> pos;
    lInt counted;
    lInt one;
    one.v[0]= 1;
    requested  = requested + one;
    for(int i = 0; i<P*N; i++){
      while(dp[i][cur_pos]+counted<requested){
        counted = counted + dp[i][cur_pos];
        cur_pos++;
      }
      pos.push_back(cur_pos);
    }

    for(auto e: pos){
      send(e);
      //cout<<e<<endl;
    }


  }

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;

const int MOD = (1<<8);
const int LEN = 90;
struct lInt{
    vector<int> v;
    lInt(){
        v= vector<int>(LEN);
    };
    lInt(long long l){
        v= vector<int>(LEN);
        int i=0;
        while(l>0){
            v[i] = l%MOD;
            l/=MOD;
            i++;
        }
    }
    lInt operator+(const lInt& rh){
        lInt res;
        int carry = 0;
        for(int i = 0; i<LEN; i++){
            int r = v[i] + rh.v[i] + carry;
            res.v[i] = r%MOD;
            carry = r/MOD;
        }
        assert(carry == 0);
        return res;
    }

    bool operator<(const lInt& rh)const{
      for(int i = LEN-1; i>=0; i--){
        if(v[i]!=rh.v[i]){
          return v[i]<rh.v[i];
        }
      }
      return false; 
    }

    long long to_ll(){
        long long res= 0;
        for(int i = LEN-1; i>=0; i--){
            res *= MOD;
            res += v[i];
        }
        return res;
    }
};

const int P = 5;
const int K = (1<<8);
vector<vector<lInt>> dp2;

void calc_dp2(int N){
  for(int i = 0; i<K; i++){
    dp2[P*N-1][i].v[0] = 1;
  }

  for(int step = P*N -2; step>=0; step--){
    lInt pref;
    for(int i = K-1; i>=0; i--){
      pref = pref + dp2[step+1][i];
      dp2[step][i] = pref;
    }
  }
}

void decode(int N, int L, int X[])
{
  dp2 = vector<vector<lInt>>(P*N + 1, vector<lInt>((1<<8)));
  calc_dp2(N);
  sort(&X[0], &X[L]);
  lInt res;
  int cur =0;
  for(int i = 0; i<L; i++){
    for(int j = cur; j<X[i]; j++){
      res = (res +dp2[i][j]);
      //cout<<"mid "<<res.to_ll()<<endl;
      cur = X[i];
    }
  }

  //cout<<"res "<<res.to_ll()<<endl;
  for(int i = 0; i<N; i++){
    //cout<<res.v[N-i-1]<<" ";
    output(res.v[N-i-1]);
  }
}

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