Submission #1004870

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

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

const int MAGIC = 7;

const int base[] = {2, 3, 3, 3, 3, 3, 3};

vector<vector<int>> devise_strategy(int n) {
  vector<vector<int>> ans(21, vector<int>(n + 1));
  function<void(int, int, int, int)> Solve = [&](int x, int b, int L, int R) {
    ans[x][0] = (b % 2 == 0 ? 0 : 1);
    if (L >= R) {
      return;
    }
    ans[x][L] = (b % 2 == 0 ? -1 : -2);
    ans[x][R] = (b % 2 == 0 ? -2 : -1);
    ++L; --R;
    if (L > R) {
      return;
    }
    int len = R - L + 1;
    int cur = L;
    vector<int> v(1, L);
    for (int i = 0; i + 1 < base[b]; i++) {
      cur += (len + base[b] - 1) / base[b];
      v.push_back(cur);
    }
    v.push_back(R + 1);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i + 1 < (int) v.size(); i++) {
      int from = v[i];
      int to = v[i + 1] - 1;
      for (int v = L - 1; v < from; v++) {
        ans[3 * (MAGIC - b - 1) + i + 1][v] = (b % 2 == 0 ? -2 : -1);
      }
      for (int v = from; v <= to; v++) {
        ans[x][v] = 3 * (MAGIC - b - 1) + i + 1;
      }
      Solve(3 * (MAGIC - b - 1) + i + 1, b - 1, from, to);
      for (int v = to + 1; v <= R + 1; v++) {
        ans[3 * (MAGIC - b - 1) + i + 1][v] = (b % 2 == 0 ? -1 : -2);
      }
    }
  };
  Solve(0, MAGIC - 1, 1, n);
  return ans;
}

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