Submission #1092577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092577		TAMREF	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	7 ms	1116 KiB

prison

#include "prison.h"

#include <vector>
#include <tuple>
#include <utility>
#include <map>
#include <cassert>
#include <deque>

using namespace std;
using ti = tuple<int, int, int, int>;

const int S[10] = {2, 2, 3, 3, 2, 3, 2, 2, 1};
const int O[10] = {1, 3, 5, 8, 11, 13, 16, 18, 20};

const int A_SMALL = -1;
const int B_SMALL = -2;

vector<vector<int>> devise_strategy(int N) {
  deque<ti> V;

  V.emplace_back(0, 0, 1, N);
  
  vector<vector<int>> ans(21, vector<int>(N+1));

  while (!V.empty()) {
    auto [n, l, s, e] = V.front(); V.pop_front();

    int me_small = (l & 1 ? B_SMALL : A_SMALL);
    int me_big = (l & 1 ? A_SMALL : B_SMALL);

    ans[n][0] = (l & 1);
    ans[n][s] = me_small;
    ans[n][e] = me_big;

    if(e - s <= 1) continue;

    int q = (e - s - 1) / S[l];
    int r = (e - s - 1) % S[l];

    int a = s + 1;
    for(int i = 0; i < S[l]; i++) {
      int b = a + (q + (i < r)) - 1;

      int ch = O[l] + i;
      V.emplace_back(ch, l+1, a, b);

      for(int j = s; j < a; j++) ans[ch][j] = me_big;
      for(int j = b + 1; j <= e; j++) ans[ch][j] = me_small;

      for(int j = a; j <= b; j++) ans[n][j] = ch;

      a = b + 1;
    }
  }

  return ans; 
}

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