제출 #666248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666248		peijar	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	14 ms	1152 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<vector<int>> strategy(k, vector<int>(N + 1));

  auto getBit = [&](int x, int bit) { return x / puissances[bit] % 3; };

  for (int i = 0; i < k; ++i) {
    if (i == 0) {
      strategy[i][0] = !((nbBits - 1) % 2);
      for (int j = 0; j < N; ++j)
        strategy[i][j + 1] = 1 + getBit(j, nbBits - 1) * nbBits + nbBits - 1;
    } else {
      int bit = (i - 1) % nbBits;
      int val = (i - 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);
          strategy[i][j + 1] = 1 + nxtVal * nbBits + bit - 1;
        }
      }
    }
  }
  return strategy;
}

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