Submission #628417

#	Time	Username	Problem	Language	Result	Execution time	Memory
628417		600Mihnea	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	74 ms	968 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

std::vector<std::vector<int>> devise_strategy(int n) {
  vector<int> dp(n + 1), par(n + 1, 0);
  for (int i = 0; i <= n; i++) {
    if (i <= 2) {
      dp[i] = 0;
      continue;
    }
    dp[i] = i;
    for (int j = 1; j <= (i - 2); j++) {
      dp[i] = min(dp[i], dp[j] + ((i - 2 + j - 1) / j));
      if (dp[j] + ((i - 2 + j - 1) / j) == dp[i]) {
        par[i] = j;
      }
    }
  }
  int x = dp[n];
  vector<int> dims;
  vector<vector<int>> what(x + 1, vector<int> (n + 1, 0));
  {
    int current = n;
    while (current >= 3) {
      dims.push_back(current);
      current = par[current];
    }
    dims.push_back(current);
  }
  vector<int> position(x + 1, 0);
  int current = 0;
  position[current++] = 0;
  for (int i = 0; i + 1 < (int) dims.size(); i++) {
    int now_len = dims[i];
    int new_len = dims[i + 1];
    int times = ((now_len - 2) + (new_len - 1)) / (new_len);
    for (int j = 1; j <= times; j++) {
      position[current++] = i + 1;
    }
  }
  function<void(int, int, int, int)> dfs = [&] (int state, int turn, int l, int r) {
    what[state][0] = turn;
    if (!(l + 1 <= r)) {
      return;
    }
    if (turn == 0) {
      what[state][l] = -1;
      what[state][r] = -2;
    } else {
      what[state][l] = -2;
      what[state][r] = -1;
    }
    if (l + 1 <= r - 1) {
      int st = l + 1, dr = r - 1;
      int last = state;
      while (last + 1 < (int) position.size() && position[last + 1] == position[last]) {
        last++;
      }

      int now_len = dims[position[state]];
      int new_len = dims[position[state] + 1];
      int times = ((now_len - 2) + (new_len - 1)) / (new_len);

      vector<vector<int>> guys;
      vector<int> states;

      for (int iter = 1; iter <= times; iter++) {
        int l2 = st, r2 = min(dr, st + new_len - 1);
        guys.push_back({});
        states.push_back(last + iter);
        for (int num = l2; num <= r2; num++) {
          what[state][num] = last + iter;
          guys.back().push_back(num);
        }
        dfs(last + iter, turn ^ 1, l2, r2);
        st = r2 + 1;
      }

      for (int i0 = 0; i0 < (int) guys.size(); i0++) {
        if (turn == 1) {
          what[states[i0]][l] = -1;
          what[states[i0]][r] = -2;
        } else {
          what[states[i0]][l] = -2;
          what[states[i0]][r] = -1;
        }
        for (int i1 = 0; i1 < (int) guys.size(); i1++) {
          if (i0 == i1) continue;
          int who = (i0 < i1) ^ turn ^ 1;
          for (auto &yy : guys[i1]) {
            if (who == 0) {
              what[states[i0]][yy] = -1;
            } else {
              what[states[i0]][yy] = -2;
            }
          }

        }
      }
    }
  };
  dfs(0, 0, 1, n);
  return what;
}

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