Submission #922548

#	Time	Username	Problem	Language	Result	Execution time	Memory
922548		kim	Parrots (IOI11_parrots)	C++17	100 / 100	1950 ms	216364 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
namespace Encode{


struct bignum{
  int base=256,len=320;
  array<int,320> a;
  bignum(int x=0){
    for(int i=0;i<len;++i) a[i]=x%base,x/=base;
  }
  bignum& operator+=(const bignum &o){
    for(int i=0;i<len;++i){
      a[i]+=o.a[i];
      if(a[i]>=base) a[i]-=base,++a[i+1];
    }
    return *this;
  }
  bignum& operator-=(const bignum &o){
    for(int i=0;i<len;++i){
      a[i]-=o.a[i];
      if(a[i]<0) a[i]+=base,--a[i+1];
    }
    return *this;
  }
  int cmp(const bignum &r){
    for(int i=len-1;i>=0;--i){
      if(a[i]!=r.a[i]) return a[i]<r.a[i]?-1:1;
    }
    return 0;
  }
  bool operator<(const bignum &o){return this->cmp(o)==-1;}
  bool operator>(const bignum &o){return this->cmp(o)==1;}
  bool operator<=(const bignum &o){return !(*this>o);}
};

bool ok=0;
bignum dp[325][260];
void f(){
  ok=1;
  int n=325,m=260;
  for(int j=0;j<m;++j) dp[1][j]=1;
  for(int i=2;i<n;++i){
    bignum sum;
    for(int j=0;j<m;++j){
      sum+=dp[i-1][j];
      dp[i][j]=sum;
    }
  }
}


}; using namespace Encode;
void encode(int N, int M[])
{
  if(!ok) f();
  bignum num;
  for(int i=0;i<N;++i) num.a[i]=M[i];
  int L=5*N;
  vector<int> vec(L);
  for(int i=L-1;num>0&&i>=0;--i){
    int id=0;
    while(dp[i+1][id]<=num) num-=dp[i+1][id++];
    vec[i]=id;
  }
  for(auto &e:vec) send(e);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
namespace Decode{


struct bignum{
  int base=256,len=320;
  array<int,320> a;
  bignum(int x=0){
    for(int i=0;i<len;++i) a[i]=x%base,x/=base;
  }
  bignum& operator+=(const bignum &o){
    for(int i=0;i<len;++i){
      a[i]+=o.a[i];
      if(a[i]>=base) a[i]-=base,++a[i+1];
    }
    return *this;
  }
};

bool ok=0;
bignum dp[325][260];
void f(){
  ok=1;
  int n=325,m=260;
  for(int j=0;j<m;++j) dp[1][j]=1;
  for(int i=2;i<n;++i){
    bignum sum;
    for(int j=0;j<m;++j){
      sum+=dp[i-1][j];
      dp[i][j]=sum;
    }
  }
}


}; using namespace Decode;
void decode(int N, int L, int X[])
{
  if(!ok) f();
  sort(X,X+L);
  bignum num;
  for(int i=0;i<L;++i){
    for(int j=0;j<X[i];++j) num+=dp[i+1][j];
  }
  for(int i=0;i<N;++i) output(num.a[i]);
}

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