Submission #464946

#	Time	Username	Problem	Language	Result	Execution time	Memory
464946		AlexLuchianov	Question (Grader is different from the original contest) (CEOI14_question_grader)	C++14	100 / 100	4068 ms	24336 KiB

encoder

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
}

decoder

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 / 100