Submission #626804

#	Time	Username	Problem	Language	Result	Execution time	Memory
626804		flashmt	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1020 KiB

prison

#include <bits/stdc++.h>
using namespace std;
const int oo = 27081993;

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

  function<void(int, int)> solve = [&](int turn, int row)
  {
    int low = from[row], high = to[row];
    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
    {
      from[turn * 3 + 1] = from[turn * 3 + 2] = oo;
      for (int i = 0; i < rem; i++)
      {
        int nextRow = turn * 3 + i / 2 + 1;
        ans[row][low + i] = nextRow;
        from[nextRow] = min(from[nextRow], low + i);
        to[nextRow] = low + i + 1;
      }
      nextRows.push_back(turn * 3 + 1);
      if (rem > 2)
        nextRows.push_back(turn * 3 + 2);
    }
    else // divide into 3 blocks
    {
      for (int i = 0; i < 3; i++)
        from[turn * 3 + i + 1] = oo;
      int each = (rem + 2) / 3;
      for (int i = 0; i < rem; i++)
      {
        int nextRow = turn * 3 + i / each + 1;
        ans[row][low + i] = nextRow;
        from[nextRow] = min(from[nextRow], low + i);
        to[nextRow] = low + i + 1;
      }
      for (int i = 0; i < 3; i++)
        nextRows.push_back(turn * 3 + i + 1);
    }

    for (int i = 0; i < size(nextRows); i++)
    {
      int curRow = nextRows[i];
      ans[curRow][low - 1] = -otherBag - 1;
      ans[curRow][high] = -curBag - 1;
      for (int j = 0; j < size(nextRows); j++)
        if (j != i)
        {
          int otherRow = nextRows[j];
          for (int v = from[otherRow]; v < to[otherRow]; v++)
            ans[curRow][v] = -(curRow < otherRow ? curBag : otherBag) - 1;
        }

      solve(turn + 1, curRow);
    }
  };

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

Compilation message (stderr)

prison.cpp: In lambda function:
prison.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < size(nextRows); i++)
      |                     ~~^~~~~~~~~~~~~~~~
prison.cpp:62:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |       for (int j = 0; j < size(nextRows); j++)
      |                       ~~^~~~~~~~~~~~~~~~

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