Submission #116798

#	Time	Username	Problem	Language	Result	Execution time	Memory
116798		dragonslayerit	Parrots (IOI11_parrots)	C++14	Compilation error	0 ms	0 KiB

encoder

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

namespace{
  struct BigNum{
    //LSB first
    std::vector<int> 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];
}

void decode(int N, int L, int X[])
{
  for(int i=0;i<=N*2;i++){
    pascal[i][0]=BigNum(1);
  }
  for(int j=0;j<=255;j++){
    pascal[0][i]=BigNum(1);
  }
  for(int i=1;i<=N*2;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]);
  }
}

decoder

Compilation message (stderr)

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++){
                   ~^~~~~~~~~~~~~~~~~~
encoder.cpp: In function 'void decode(int, int, int*)':
encoder.cpp:94:15: error: 'i' was not declared in this scope
     pascal[0][i]=BigNum(1);
               ^

/tmp/ccAPXr2C.o: In function `main':
grader_decoder.cpp:(.text.startup+0x1f6): undefined reference to `decode(int, int, int*)'
collect2: error: ld returned 1 exit status