Submission #114863

#	Time	Username	Problem	Language	Result	Execution time	Memory
114863		KLPP	Parrots (IOI11_parrots)	C++14	100 / 100	1653 ms	46544 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define sz 72
#define rep(i,a,b) for(int i=a;i<b;i++)
struct Bignum{
  int arr[sz];
};
Bignum sum(Bignum A,Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=(A.arr[i]+B.arr[i]+carry);
    carry=result.arr[i]/256;
    result.arr[i]%=256;
  }
  return result;
}
bool Bigger(Bignum A, Bignum B){
  for(int i=sz-1;i>-1;i--){
    if(A.arr[i]>B.arr[i])return true;
    if(A.arr[i]<B.arr[i])return false;
  }
  return true;
}
Bignum difference(Bignum A, Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=A.arr[i]-B.arr[i]-carry;
    if(result.arr[i]<0){
      result.arr[i]+=256;
      carry=1;
    }else{
      carry=0;
    }
  }
  return result;
}
void print(Bignum A){
  for(int i=sz-1;i>-1;i--){
    cout<<A.arr[i]<<" ";
  }cout<<endl;
}
bool visited[400][256];
Bignum table[400][256];
void comb(int a, int b){
  //cout<<a<<" "<<b<<endl;
  if(visited[a][b])return;
  
  if(a>0 && b>0){
    comb(a,b-1);
    comb(a-1,b);
    table[a][b]=sum(table[a-1][b],table[a][b-1]);
    
  }
  else table[a][b]=table[0][0];
  visited[a][b]=true;
}
void encode(int N, int M[])
{
  int n=N;
  //n=64;
  rep(i,0,5*n+5){
    rep(j,0,256)visited[i][j]=false;
  }
  visited[0][0]=true;
  rep(i,0,sz)table[0][0].arr[i]=0;
  table[0][0].arr[0]=1;
  int floor=(9*n)/2;
  //cout<<floor<<endl;
  //comb(5*n,255);
  //print(table[floor][255]);
  Bignum target;
  rep(i,0,sz)target.arr[i]=0;
  rep(i,0,n)target.arr[i]=M[i];
  //target=sum(target,table[0][0]);
  for(int i=5*n-1;i>-1;i--){
    /*int hi=-1;
    rep(j,0,255){
      if(!Bigger(target,table[i+1][j])){
	hi=j;
	j=256;
      }
      }*/
    int lo=-1;
    int hi=255;
    while(hi-lo>1){
      //cout<<lo<<" "<<hi<<endl;
      int mid=(hi+lo)/2;
      comb(i+1,mid);
      if(!Bigger(target,table[i+1][mid]))hi=mid;
      else lo=mid;
    }
    if(hi>0){
      target=difference(target,table[i+1][hi-1]);
    }
    //cout<<hi<<endl;
    send(hi);
  }
  //comb(6,5);
  //print(table[6][5]);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define sz 72
#define rep(i,a,b) for(int i=a;i<b;i++)
bool Visited[400][256];

struct Bignum{
  int arr[sz];
};
Bignum Table[400][256];
Bignum Sum(Bignum A,Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=(A.arr[i]+B.arr[i]+carry);
    carry=result.arr[i]/256;
    result.arr[i]%=256;
  }
  return result;
}
bool bigger(Bignum A, Bignum B){
  for(int i=sz-1;i>-1;i--){
    if(A.arr[i]>B.arr[i])return true;
    if(A.arr[i]<B.arr[i])return false;
  }
  return false;
}
Bignum Difference(Bignum A, Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=A.arr[i]-B.arr[i]-carry;
    if(result.arr[i]<0){
      result.arr[i]+=256;
      carry=1;
    }else{
      carry=0;
    }
  }
  return result;
}

void Comb(int a, int b){
  //cout<<a<<" "<<b<<endl;
  if(Visited[a][b])return;
  
  if(a>0 && b>0){
    Comb(a,b-1);
    Comb(a-1,b);
    Table[a][b]=Sum(Table[a-1][b],Table[a][b-1]);
    
  }
  else Table[a][b]=Table[0][0];
  Visited[a][b]=true;
}
void decode(int N, int L, int X[])
{
  int n=N;
  
  rep(i,0,5*n+5){
    rep(j,0,256)Visited[i][j]=false;
  }
  Visited[0][0]=true;
  rep(i,0,sz)Table[0][0].arr[i]=0;
  Table[0][0].arr[0]=1;
  
  
  sort(X,X+L);
  Bignum target;
  rep(i,0,sz)target.arr[i]=0;
  rep(i,0,L){
    if(X[i]>0){
      Comb(i+1,X[i]-1);
      target=Sum(target,Table[i+1][X[i]-1]);
    }
  }
  rep(i,0,n)output(target.arr[i]);
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:71:7: warning: unused variable 'floor' [-Wunused-variable]
   int floor=(9*n)/2;
       ^~~~~

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