Submission #509632

#	Time	Username	Problem	Language	Result	Execution time	Memory
509632		HappyPacMan	Parrots (IOI11_parrots)	C++14	81 / 100	2489 ms	197324 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[]){
  memset(curr,0,sizeof(curr));
  memset(comb,0,sizeof(comb));
  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;
  };
  for(int i=1;i<257;i++) comb[0][0][i] = 1;
  int maxx = 1;
  for(int i=1;i<1500;i++){
    bool v = false;
    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;
      }
      if(valid(i,j)){
        v = true;
        break;
      }
    }
    if(v) 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[]){
  memset(ans,0,sizeof(ans));
  memset(temp,0,sizeof(temp));
  sort(X,X+L);
  for(int i=1;i<257;i++) temp[0][0][i] = 1;
  for(int i=1;i<=L;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;
      }
    }
    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]);
}

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