Submission #509666

#	Time	Username	Problem	Language	Result	Execution time	Memory
509666		HappyPacMan	Parrots (IOI11_parrots)	C++14	100 / 100	374 ms	197228 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
int curr[65],comb[65][1500][257];

void encode(int N, int M[]){
  if(comb[64][1499][256] == 0){
    for(int i=1;i<257;i++) comb[0][0][i] = 1;
    int maxx = 1;
    for(int i=1;i<1500;i++){
      for(int j=1;j<257;j++){
        for(int k=0;k<65;k++){
          comb[k][i][j] += comb[k][i-1][j]+comb[k][i][j-1];
          if(k != 64){
            comb[k+1][i][j] += comb[k][i][j]/256;
            comb[k][i][j] %= 256;
          }
        }
        comb[64][i][j] = min(comb[64][i][j],4);
      }
    }
  }
  for(int i=0;i<N;i++) curr[i] = M[i];
  auto valid = [&](int i,int j){
    for(int k=65;k>0;k--){
      if(comb[k-1][i][j] > curr[k-1]) return true;
      else if(comb[k-1][i][j] < curr[k-1]) return false;
    }
    return false;
  };
  int maxx = 1;
  for(int i=1;i<1500;i++){
    if(valid(i,256)) break;
    maxx++;
  }
  for(int i=maxx;i>0;i--){
    for(int j=1;j<257;j++){
      if(valid(i,j)){
        send(j-1);
        for(int k=0;k<65;k++){
          curr[k] -= comb[k][i][j-1];
          if(curr[k] < 0){
            int left = (255-curr[k])/256;
            if(k != 64) curr[k+1] -= left;
            curr[k] += 256*left;
          }
        }
        break;
      }
    }
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
int ans[65],temp[65][1500][257];

void decode(int N, int L, int X[]){
  if(temp[64][1499][256] == 0){
    for(int i=1;i<257;i++) temp[0][0][i] = 1;
    int maxx = 1;
    for(int i=1;i<1500;i++){
      for(int j=1;j<257;j++){
        for(int k=0;k<65;k++){
          temp[k][i][j] += temp[k][i-1][j]+temp[k][i][j-1];
          if(k != 64){
            temp[k+1][i][j] += temp[k][i][j]/256;
            temp[k][i][j] %= 256;
          }
        }
        temp[64][i][j] = min(temp[64][i][j],4);
      }
    }
  }
  sort(X,X+L);
  memset(ans,0,sizeof(ans));
  for(int i=1;i<=L;i++){
    for(int k=0;k<65;k++){
      ans[k] += temp[k][i][X[i-1]];
      if(k != 64) ans[k+1] += ans[k]/256;
      ans[k] %= 256;
    }
  }
  for(int i=0;i<N;i++) output(ans[i]);
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:10:9: warning: unused variable 'maxx' [-Wunused-variable]
   10 |     int maxx = 1;
      |         ^~~~

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:10:9: warning: unused variable 'maxx' [-Wunused-variable]
   10 |     int maxx = 1;
      |         ^~~~

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