oj.uz

Submission #116801

# Submission time Handle Problem Language Result Execution time Memory
116801 2019-06-13T22:19:53 Z dragonslayerit Parrots (IOI11_parrots) C++14
100 / 100
 1558 ms 21768 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <vector>
#include <cassert>
#include <string>

namespace{
  struct BigNum{
    //LSB first
    std::vector<short> digits;
    BigNum(){
    }
    BigNum(int num):digits({num}){
      normalize();
    }
    BigNum(std::string num){
      for(int i=0;i<num.size();i++){
	*this+=*this+*this+*this+*this;
	*this+=*this;
	*this+=BigNum(num[i]-'0');
      }
    }
    BigNum(const char* num){
      for(int i=0;num[i];i++){
	*this+=*this+*this+*this+*this;
	*this+=*this;
	*this+=BigNum(num[i]-'0');
      }
    }
    BigNum& normalize(){
      int carry=0;
      for(int i=0;i<digits.size();i++){
	digits[i]+=carry;
	int mod=digits[i]&255;
	int div=(digits[i]-mod)>>8;
	carry=div;
	digits[i]=mod;
      }
      assert(carry>=0);
      assert(carry<256);
      if(carry){
	digits.push_back(carry);
      }
      while(digits.size()&&digits.back()==0) digits.pop_back();
      return *this;
    }
    BigNum& operator+=(BigNum num){
      if(digits.size()<num.digits.size()) std::swap(digits,num.digits);
      for(int i=0;i<num.digits.size();i++){
	digits[i]+=num.digits[i];
      }
      return normalize();
    }
    BigNum& operator-=(BigNum num){
      assert(digits.size()>=num.digits.size());
      for(int i=0;i<num.digits.size();i++){
	digits[i]-=num.digits[i];
      }
      return normalize();
    }
    BigNum operator+(BigNum num)const{
      return num+=*this;
    }
    bool operator<(BigNum num)const{
      if(digits.size()!=num.digits.size()) return digits.size()<num.digits.size();
      for(int i=(int)digits.size()-1;i>=0;i--){
	if(digits[i]!=num.digits[i]){
	  return digits[i]<num.digits[i];
	}
      }
      return false;
    }
    bool operator==(BigNum num)const{
      return !(*this<num)&&!(num<*this);
    }
    bool operator!=(BigNum num)const{
      return !(*this==num);
    }
    void hexdump(){
      for(int i=(int)digits.size()-1;i>=0;i--){
	fprintf(stderr,"%02x",digits[i]);
      }
    }
  };
  struct BigNum pascal[400][400];
  const int P=5;
}

void encode(int N, int M[])
{
  for(int i=0;i<=N*P;i++){
    pascal[i][0]=BigNum(1);
  }
  for(int j=0;j<=255;j++){
    pascal[0][j]=BigNum(1);
  }
  for(int i=1;i<=N*P;i++){
    for(int j=1;j<=255;j++){
      pascal[i][j]=pascal[i-1][j]+pascal[i][j-1];
    }
  }
  struct BigNum num;
  for(int i=0;i<N;i++){
    num.digits.push_back(M[i]);
  }
  num.normalize();
  //num.hexdump(),fprintf(stderr,"\n");
  int zeros=N*P,ones=255;
  assert(num<pascal[zeros][ones]);
  
  std::vector<int> bits;
  while(zeros+ones>0){
    //fprintf(stderr,"zeros=%d,ones=%d\n",zeros,ones);
    if(zeros>0&&num<pascal[zeros-1][ones]){
      //num.hexdump(),fprintf(stderr," < "),pascal[zeros-1][ones].hexdump(),fprintf(stderr,"\n");
      bits.push_back(0);
      zeros--;
    }else{
      if(zeros>0){
	//num.hexdump(),fprintf(stderr," >= "),pascal[zeros-1][ones].hexdump(),fprintf(stderr,"\n");
	//fprintf(stderr,"Add "),pascal[zeros-1][ones].hexdump(),fprintf(stderr,"\n");
	num-=pascal[zeros-1][ones];
      }
      bits.push_back(1);
      ones--;
    }
  }
  assert(zeros==0);
  assert(ones==0);
  /*
  fprintf(stderr,"E:");
  for(int x:bits){
    fprintf(stderr,"%d",x);
  }
  fprintf(stderr,"\n");
  */
  int curr=0;
  for(int x:bits){
    if(x){
      curr++;
    }else{
      send(curr);
    }
  }
  assert(curr==255);
}

#include "decoder.h"
#include "decoderlib.h"
#include <vector>
#include <cassert>
#include <string>

namespace{
  struct BigNum{
    //LSB first
    std::vector<short> digits;
    BigNum(){
    }
    BigNum(int num):digits({num}){
      normalize();
    }
    BigNum(std::string num){
      for(int i=0;i<num.size();i++){
	*this+=*this+*this+*this+*this;
	*this+=*this;
	*this+=BigNum(num[i]-'0');
      }
    }
    BigNum(const char* num){
      for(int i=0;num[i];i++){
	*this+=*this+*this+*this+*this;
	*this+=*this;
	*this+=BigNum(num[i]-'0');
      }
    }
    BigNum& normalize(){
      int carry=0;
      for(int i=0;i<digits.size();i++){
	digits[i]+=carry;
	int mod=digits[i]&255;
	int div=(digits[i]-mod)>>8;
	carry=div;
	digits[i]=mod;
      }
      assert(carry>=0);
      assert(carry<256);
      if(carry){
	digits.push_back(carry);
      }
      while(digits.size()&&digits.back()==0) digits.pop_back();
      return *this;
    }
    BigNum& operator+=(BigNum num){
      if(digits.size()<num.digits.size()) std::swap(digits,num.digits);
      for(int i=0;i<num.digits.size();i++){
	digits[i]+=num.digits[i];
      }
      return normalize();
    }
    BigNum& operator-=(BigNum num){
      assert(digits.size()>=num.digits.size());
      for(int i=0;i<num.digits.size();i++){
	digits[i]-=num.digits[i];
      }
      return normalize();
    }
    BigNum operator+(BigNum num)const{
      return num+=*this;
    }
    bool operator<(BigNum num)const{
      if(digits.size()!=num.digits.size()) return digits.size()<num.digits.size();
      for(int i=(int)digits.size()-1;i>=0;i--){
	if(digits[i]!=num.digits[i]){
	  return digits[i]<num.digits[i];
	}
      }
      return false;
    }
    bool operator==(BigNum num)const{
      return !(*this<num)&&!(num<*this);
    }
    bool operator!=(BigNum num)const{
      return !(*this==num);
    }
    void hexdump(){
      for(int i=(int)digits.size()-1;i>=0;i--){
	fprintf(stderr,"%02x",digits[i]);
      }
    }
  };
  struct BigNum pascal[400][400];
  const int P=5;
}

void decode(int N, int L, int X[])
{
  for(int i=0;i<=N*P;i++){
    pascal[i][0]=BigNum(1);
  }
  for(int j=0;j<=255;j++){
    pascal[0][j]=BigNum(1);
  }
  for(int i=1;i<=N*P;i++){
    for(int j=1;j<=255;j++){
      pascal[i][j]=pascal[i-1][j]+pascal[i][j-1];
    }
  }
  std::vector<int> cnt(256);
  for(int i=0;i<L;i++){
    cnt[X[i]]++;
  }
  std::vector<int> bits;
  for(int i=0;i<256;i++){
    while(cnt[i]--){
      bits.push_back(0);
    }
    bits.push_back(1);
  }
  bits.pop_back();
  /*
  fprintf(stderr,"D:");
  for(int x:bits){
    fprintf(stderr,"%d",x);
  }
  fprintf(stderr,"\n");
  */
  struct BigNum num;
  int zeros=0,ones=0;
  for(int i=(int)bits.size()-1;i>=0;i--){
    if(bits[i]){
      ones++;
      if(zeros>0){
	//fprintf(stderr,"Add "),pascal[zeros-1][ones].hexdump(),fprintf(stderr,"\n");
	num+=pascal[zeros-1][ones];
      }
    }else{
      zeros++;
    }
  }
  //num.hexdump(),fprintf(stderr,"\n");
  num.digits.resize(N);
  for(int i=0;i<N;i++){
    output(num.digits[i]);
  }
}

Compilation message

encoder.cpp: In constructor '{anonymous}::BigNum::BigNum(int)':
encoder.cpp:13:33: warning: narrowing conversion of 'num' from 'int' to 'short int' inside { } [-Wnarrowing]
     BigNum(int num):digits({num}){
                                 ^
encoder.cpp:13:33: warning: narrowing conversion of 'num' from 'int' to 'short int' inside { } [-Wnarrowing]
encoder.cpp: In constructor '{anonymous}::BigNum::BigNum(std::__cxx11::string)':
encoder.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<num.size();i++){
                   ~^~~~~~~~~~~
encoder.cpp: In member function '{anonymous}::BigNum& {anonymous}::BigNum::normalize()':
encoder.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<digits.size();i++){
                   ~^~~~~~~~~~~~~~
encoder.cpp: In member function '{anonymous}::BigNum& {anonymous}::BigNum::operator+=({anonymous}::BigNum)':
encoder.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<num.digits.size();i++){
                   ~^~~~~~~~~~~~~~~~~~
encoder.cpp: In member function '{anonymous}::BigNum& {anonymous}::BigNum::operator-=({anonymous}::BigNum)':
encoder.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<num.digits.size();i++){
                   ~^~~~~~~~~~~~~~~~~~

decoder.cpp: In constructor '{anonymous}::BigNum::BigNum(int)':
decoder.cpp:13:33: warning: narrowing conversion of 'num' from 'int' to 'short int' inside { } [-Wnarrowing]
     BigNum(int num):digits({num}){
                                 ^
decoder.cpp:13:33: warning: narrowing conversion of 'num' from 'int' to 'short int' inside { } [-Wnarrowing]
decoder.cpp: In constructor '{anonymous}::BigNum::BigNum(std::__cxx11::string)':
decoder.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<num.size();i++){
                   ~^~~~~~~~~~~
decoder.cpp: In member function '{anonymous}::BigNum& {anonymous}::BigNum::normalize()':
decoder.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<digits.size();i++){
                   ~^~~~~~~~~~~~~~
decoder.cpp: In member function '{anonymous}::BigNum& {anonymous}::BigNum::operator+=({anonymous}::BigNum)':
decoder.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<num.digits.size();i++){
                   ~^~~~~~~~~~~~~~~~~~
decoder.cpp: In member function '{anonymous}::BigNum& {anonymous}::BigNum::operator-=({anonymous}::BigNum)':
decoder.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<num.digits.size();i++){
                   ~^~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9088 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 9712 KB Output is correct
2 Correct 182 ms 10304 KB Output is correct
3 Correct 256 ms 10648 KB Output is correct
4 Correct 273 ms 10992 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 9632 KB Output is correct
2 Correct 183 ms 10384 KB Output is correct
3 Correct 253 ms 10736 KB Output is correct
4 Correct 278 ms 10736 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 9752 KB Output is correct
2 Correct 276 ms 10944 KB Output is correct
3 Correct 364 ms 11888 KB Output is correct
4 Correct 609 ms 13552 KB Output is correct
5 Correct 610 ms 13768 KB Output is correct
6 Correct 639 ms 13888 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 11096 KB Output is correct - P = 5.000000
2 Correct 645 ms 14184 KB Output is correct - P = 5.000000
3 Correct 643 ms 14064 KB Output is correct - P = 5.000000
4 Correct 1096 ms 18032 KB Output is correct - P = 5.000000
5 Correct 1541 ms 20720 KB Output is correct - P = 5.000000
6 Correct 1548 ms 21592 KB Output is correct - P = 5.000000
7 Correct 1558 ms 21768 KB Output is correct - P = 5.000000