Submission #1223744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223744		trimkus	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	11 ms	21060 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int N) {
  vector<vector<int>> res(1, vector<int>(N + 1));
  res[0][1] = -1;
  res[0][N] = -2;
  int jump = 10;
  auto dfs = [&](auto& dfs, int i, int till, int idx) -> void {
      vector<int> add(N + 1);
      add[0] = idx;
      for (int j = 1; j <= i; ++j) {
          add[j] = (idx ? -2 : -1);
      }
      for (int j = till; j <= N; ++j) {
        add[j] = (idx ? -1 : -2);
      }
      
      for (int j = i + 1; j < till; ++j) {
        add[j] = res.size() + 1;
      }
      res.push_back(add);
      if (i + 1 < till) {
        int mid = (i + till) / 2;
        dfs(dfs, i, mid, idx ^ 1);
        dfs(dfs, mid + 1, till, idx ^ 1);
      }
  };
  for (int i = 2; i < N; i += jump) {
      int till = min(N - 1, i + jump - 1);
      for (int j = i; j <= till; ++j) {
          res[0][j] = res.size();
      }
      dfs(dfs, i, till, 1);
  }
  // for (auto& v : res) {
  //   for (auto& u : v) {
  //     cerr << u << " ";
  //   }
  //   cerr << "\n";
  // }
  // cerr << "\n";
  return res;
}

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