Submission #666229

#	Time	Username	Problem	Language	Result	Execution time	Memory
666229		peijar	Prisoner Challenge (IOI22_prison)	C++17	36.50 / 100	18 ms	1620 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 = 3 * nbBits + 1;
  vector<vector<int>> strategy(k, vector<int>(N + 1));

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

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