oj.uz

Submission #509666

# Submission time Handle Problem Language Result Execution time Memory
509666 2022-01-14T07:59:03 Z HappyPacMan Parrots (IOI11_parrots) C++14
100 / 100
 374 ms 197228 KB 
#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;
      }
    }
  }
}

#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 196784 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 196936 KB Output is correct
2 Correct 345 ms 196948 KB Output is correct
3 Correct 292 ms 197028 KB Output is correct
4 Correct 273 ms 196952 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 196992 KB Output is correct
2 Correct 262 ms 196936 KB Output is correct
3 Correct 284 ms 197036 KB Output is correct
4 Correct 258 ms 197100 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 197080 KB Output is correct
2 Correct 296 ms 196984 KB Output is correct
3 Correct 306 ms 196956 KB Output is correct
4 Correct 298 ms 197204 KB Output is correct
5 Correct 272 ms 197160 KB Output is correct
6 Correct 297 ms 197048 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 197052 KB Output is correct - P = 1.750000
2 Correct 296 ms 197100 KB Output is correct - P = 2.437500
3 Correct 298 ms 197016 KB Output is correct - P = 2.484848
4 Correct 330 ms 197200 KB Output is correct - P = 3.300000
5 Correct 374 ms 197136 KB Output is correct - P = 3.850000
6 Correct 316 ms 197220 KB Output is correct - P = 4.031746
7 Correct 328 ms 197228 KB Output is correct - P = 4.093750