Submission #825539

#	Time	Username	Problem	Language	Result	Execution time	Memory
825539		LittleCube	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1072 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

vector<int> B = {},
            P = {1};
vector<int> nxt;
int bag[30];

struct state
{
  int l, r, a, b;
};



vector<state> spaces[30];
vector<vector<int>> devise_strategy(int N)
{
  vector<vector<int>> sol;
  bag[0] = 1;
  spaces[0] = {state{1, N, 1, N}};
  int x = 0;
  for (int i = 0; i < 4; i++)
  {  
    while(B.size() < P.size())
      B.emplace_back(3);
    int p = P.size();
    P.emplace_back(p + 3);
    P.emplace_back(p + 3);
    P.emplace_back(p + 3);
  }
  for (int i = 0; i <= 10; i++)
  {  
    while(B.size() < P.size())
      B.emplace_back(2);
    int p = P.size();
    P.emplace_back(p + 2);
    P.emplace_back(p + 2);
  }
  for (int j = 0; j <= x; j++)
  {
    sol.emplace_back(vector<int>(N + 1, 0));
    sol[j][0] = bag[j] - 1;
    for (auto &[l, r, a, b] : spaces[j])
    {
      for (int k = l; k <= a; k++)
        sol[j][k] = -bag[j];
      for (int k = b; k <= r; k++)
        sol[j][k] = -(bag[j] ^ 3);
      l = a + 1, r = b - 1;
    }
    for (auto [l, r, a, b] : spaces[j])
    {
      if (r < l)
        continue;
      if (B[j] == 2)
      {
        int h = (l + r) / 2;
        int p = P[j];
        bag[p] = bag[p + 1] = bag[j] ^ 3;
        if (l == r)
        {
          sol[j][l] = p;
          spaces[p].emplace_back(state{a, b, l, r});
          x = max(x, p);
        }
        else
        {
          spaces[p].emplace_back(state{a, b, l, h});
          for (int k = l; k <= h; k++)
            sol[j][k] = p;
          spaces[p + 1].emplace_back(state{a, b, h + 1, r});
          for (int k = h + 1; k <= r; k++)
            sol[j][k] = p + 1;
          x = max(x, p + 1);
        }
      }
      else
      {
        int hl = (l + l + r + 1) / 3, hr = (l + r + r + 2) / 3;
        int p = P[j];
        bag[p] = bag[p + 1] = bag[p + 2] = bag[j] ^ 3;
        if (l == r)
        {
          sol[j][l] = p;
          spaces[p].emplace_back(state{a, b, l, r});
          x = max(x, p);
        }
        else if (l + 1 == r)
        {
          sol[j][l] = p;
          spaces[p].emplace_back(state{a, b, l, l});
          sol[j][r] = p + 1;
          spaces[p + 1].emplace_back(state{a, b, r, r});
          x = max(x, p + 1);
        }
        else
        {
          spaces[p].emplace_back(state{a, b, l, hl});
          for (int k = l; k <= hl; k++)
            sol[j][k] = p;

          spaces[p + 1].emplace_back(state{a, b, hl + 1, hr});
          for (int k = hl + 1; k <= hr; k++)
            sol[j][k] = p + 1;

          spaces[p + 2].emplace_back(state{a, b, hr + 1, r});
          for (int k = hr + 1; k <= r; k++)
            sol[j][k] = p + 2;
          x = max(x, p + 2);
        }
      }
    }
  }
  // for (int i = 0; i <= x; i++)
  // {
  //   cout << sol[i][0] << " |";
  //   for (int j = 1; j <= N; j++)
  //     cout << ' ' << sol[i][j];
  //   cout << '\n';
  // }
  cerr << x << '\n';
  return sol;
}

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