oj.uz

Submission #922572

# Submission time Handle Problem Language Result Execution time Memory
922572 2024-02-05T16:55:14 Z kim Parrots (IOI11_parrots) C++17
100 / 100
 172 ms 216552 KB 
#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
namespace Encode{


struct bignum{
  short base=256,len=320;
  array<short,320> a;
  bignum(short 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;
  }
  friend bignum operator+(const bignum &l,const bignum &r){return bignum(l)+=r;}
  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],qs[325][260];
void f(){
  ok=1;
  int n=325,m=260;
  for(int j=0;j<m;++j) dp[1][j].a[0]=1,qs[1][j].a[0]=j+1;
  for(int i=2;i<n;++i){
    for(int j=0;j<m;++j){
      dp[i][j]=qs[i-1][j];
      if(j==0) qs[i][j]=dp[i][j];
      else qs[i][j]=qs[i][j-1]+dp[i][j];
    }
  }
}


}; 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;i>=0;--i){
    int l=0,r=255;
    while(l<r){
      int mid=l+r>>1;
      if(qs[i+1][mid]<=num) l=mid+1;
      else r=mid;
    }
    if(l==0) break;
    num-=qs[i+1][l-1];
    vec[i]=l;
  }
  for(auto &e:vec) send(e);
}

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


struct bignum{
  short base=256,len=320;
  array<short,320> a;
  bignum(short 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;
  }
  friend bignum operator+(const bignum &l,const bignum &r){return bignum(l)+=r;}
  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],qs[325][260];
void f(){
  ok=1;
  int n=325,m=260;
  for(int j=0;j<m;++j) dp[1][j].a[0]=1,qs[1][j].a[0]=j+1;
  for(int i=2;i<n;++i){
    for(int j=0;j<m;++j){
      dp[i][j]=qs[i-1][j];
      if(j==0) qs[i][j]=dp[i][j];
      else qs[i][j]=qs[i][j-1]+dp[i][j];
    }
  }
}


}; 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){
    if(X[i]>0) num+=qs[i+1][X[i]-1];
  }
  for(int i=0;i<N;++i) output(num.a[i]);
}

Compilation message

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:68:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |       int mid=l+r>>1;
      |               ~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 215888 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 215764 KB Output is correct
2 Correct 141 ms 215744 KB Output is correct
3 Correct 134 ms 216092 KB Output is correct
4 Correct 137 ms 216032 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 215752 KB Output is correct
2 Correct 136 ms 215996 KB Output is correct
3 Correct 135 ms 215820 KB Output is correct
4 Correct 135 ms 215876 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 215736 KB Output is correct
2 Correct 138 ms 215836 KB Output is correct
3 Correct 133 ms 215860 KB Output is correct
4 Correct 144 ms 216552 KB Output is correct
5 Correct 142 ms 215876 KB Output is correct
6 Correct 145 ms 216440 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 215756 KB Output is correct - P = 5.000000
2 Correct 143 ms 215780 KB Output is correct - P = 5.000000
3 Correct 155 ms 215840 KB Output is correct - P = 5.000000
4 Correct 157 ms 215828 KB Output is correct - P = 5.000000
5 Correct 163 ms 215808 KB Output is correct - P = 5.000000
6 Correct 166 ms 215856 KB Output is correct - P = 5.000000
7 Correct 172 ms 215936 KB Output is correct - P = 5.000000