Submission #666251

#	Time	Username	Problem	Language	Result	Execution time	Memory
666251		peijar	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	11 ms	1064 KiB

prison

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

vector<vector<int>> devise_strategy(int N) {
  int nbBits = 8;
  vector<int> puissances(nbBits);
  puissances[0] = 1;
  for (int i = 1; i < nbBits; ++i)
    puissances[i] = 3 * puissances[i - 1];
  int k = 3 * nbBits + 1;
  vector<int> states;
  states.push_back(0);
  for (int i = 1; i < k; ++i) {
    int bit = (i - 1) % nbBits;
    int val = (i - 1) / nbBits;
    if (bit or val == 1)
      states.push_back(i);
  }
  k = states.size();
  vector<vector<int>> strategy(k, vector<int>(N + 1));

  auto getBit = [&](int x, int bit) { return x / puissances[bit] % 3; };
  auto getId = [&](int x) {
    return lower_bound(states.begin(), states.end(), x) - states.begin();
  };

  for (int i = 0; i < k; ++i) {
    int s = states[i];
    if (s == 0) {
      strategy[i][0] = !((nbBits - 1) % 2);
      for (int j = 0; j < N; ++j)
        strategy[i][j + 1] =
            getId(1 + getBit(j, nbBits - 1) * nbBits + nbBits - 1);
    } else {
      int bit = (s - 1) % nbBits;
      int val = (s - 1) / nbBits;
      strategy[i][0] = bit % 2;
      for (int j = 0; j < N; ++j) {
        int v = getBit(j, bit);
        if (v < val)
          strategy[i][j + 1] = -1 - bit % 2;
        else if (v > val)
          strategy[i][j + 1] = -2 + bit % 2;
        else if (bit) {
          int nxtVal = getBit(j, bit - 1);
          if (bit == 1 and nxtVal == 0)
            strategy[i][j + 1] = -1 - bit % 2;
          else if (bit == 1 and nxtVal == 2)
            strategy[i][j + 1] = -2 + bit % 2;
          else
            strategy[i][j + 1] = getId(1 + nxtVal * nbBits + bit - 1);
        }
      }
    }
  }
  return strategy;
}

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