Submission #626797

#	Time	Username	Problem	Language	Result	Execution time	Memory
626797		flashmt	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	5 ms	852 KiB

prison

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

vector<vector<int>> devise_strategy(int n) {
  int saveN = n;
  n = 5000;
  vector<vector<int>> ans(21, vector<int>(n + 1, -1));
  for (int i = 0; i <= 20; i++)
    ans[i][0] = 0;

  function<void(int, int, int, int)> solve = [&](int turn, int row, int low, int high)
  {
    int curBag = turn % 2, otherBag = curBag ^ 1;
    ans[row][0] = curBag;
    ans[row][low++] = -curBag - 1;
    if (high > low)
      ans[row][--high] = -otherBag - 1;

    int rem = high - low;
    if (rem <= 1)
      return;

    vector<int> nextRows;
    if (rem <= 4) // divide into block of size 2
    {
      for (int i = 0; i < rem; i++)
        ans[row][low + i] = turn * 3 + i / 2 + 1;
      solve(turn + 1, turn * 3 + 1, low, min(low + 2, high));
      nextRows.push_back(turn * 3 + 1);

      if (rem > 2)
      {
        solve(turn + 1, turn * 3 + 2, low + 2, high);
        nextRows.push_back(turn * 3 + 2);
      }
    }
    else // divide into 3 blocks
    {
      int each = (rem + 2) / 3;
      for (int i = 0; i < rem; i++)
        ans[row][low + i] = turn * 3 + i / each + 1;
      for (int i = 0; i < 3; i++)
      {
        solve(turn + 1, turn * 3 + i + 1, low + i * each, min(low + i * each + each, high));
        nextRows.push_back(turn * 3 + i + 1);
      }
    }

    for (int r : nextRows)
    {
      ans[r][low - 1] = -otherBag - 1;
      ans[r][high] = -curBag - 1;
    }
  };

  solve(0, 0, 1, n + 1);
  for (int i = 0; i <= 20; i++)
    ans[i].resize(saveN + 1);
  return ans;
}

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