oj.uz

Submission #464946

# Submission time Handle Problem Language Result Execution time Memory
464946 2021-08-14T14:25:15 Z AlexLuchianov Question (Grader is different from the original contest) (CEOI14_question_grader) C++14
100 / 100
 4068 ms 24336 KB 
namespace{
  int const nmax = (1 << 12);
  int dp[1 + nmax], rev[1 + nmax];

  void precompute() {
    int ptr = 0;
    for(int mask = 0; mask < (1 << 12); mask++) {
      if(__builtin_popcount(mask) == 6) {
        dp[++ptr] = mask;
        rev[mask] = ptr;
      }
    }
  }
}

int encode(int n, int x, int y) {
  if(dp[1] == 0)
    precompute();
  for(int bit = 0; bit < 12; bit++)
    if((dp[x] & (1 << bit)) < (dp[y] & (1 << bit)))
      return 1 + bit;
  return 0; //we should not be here
}

namespace {
  int const nmax = (1 << 12);
  int dp[1 + nmax], rev[1 + nmax];

  void precompute() {
    int ptr = 0;
    for(int mask = 0; mask < (1 << 12); mask++) {
      if(__builtin_popcount(mask) == 6) {
        dp[++ptr] = mask;
        rev[mask] = ptr;
      }
    }
  }
}

int decode (int n, int q, int h) {
  if(dp[q] == 0)
    precompute();
  return (0 == (dp[q] & (1 << (h - 1))));
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4068 ms 24124 KB Output is correct - maxh = 12
2 Correct 3901 ms 24336 KB Output is correct - maxh = 12