Submission #666231

#	Time	Username	Problem	Language	Result	Execution time	Memory
666231		peijar	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	13 ms	1140 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> devise_strategy(int N) {
  int nbBits = log2(N - 1) + 1;
  int k = 2 * nbBits + 1;
  vector<vector<int>> strategy(k, vector<int>(N + 1));

  for (int i = 0; i < k; ++i) {
    if (i == 0) {
      strategy[i][0] = !((nbBits - 1) % 2);
      for (int j = 0; j < N; ++j) {
        if ((1 << (nbBits - 1)) & j)
          strategy[i][j + 1] = nbBits + 1 + (nbBits - 1);
        else
          strategy[i][j + 1] = 1 + (nbBits - 1);
      }
    } else if (i <= 2 * nbBits) {
      int bit = i <= nbBits ? i - 1 : i - nbBits - 1;
      int big = i > nbBits;
      strategy[i][0] = bit % 2;
      for (int j = 0; j < N; ++j) {
        if (big != !!((1 << bit) & j)) {
          if (big)
            strategy[i][j + 1] = -1 - bit % 2;
          else
            strategy[i][j + 1] = -2 + bit % 2;
        } else {
          if (bit == 0)
            strategy[i][j + 1] = 0;
          else {
            if ((1 << (bit - 1)) & j)
              strategy[i][j + 1] = nbBits + 1 + bit - 1;
            else
              strategy[i][j + 1] = 1 + bit - 1;
          }
        }
      }
    }
  }
  return strategy;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 46 / 90