Submission #1223812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223812		trimkus	Prisoner Challenge (IOI22_prison)	C++20	30 / 100	15 ms	2376 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;
    vector<int> add(N + 1);
    add[0] = 0;
    add[1] = -1;
    add[N] = -2;
    int bit = 1;
    res.push_back(add);
    vector<vector<int>> later;
    while ((1 << (bit + 1)) < N) bit += 1;
    for (int i = bit; i >= 0; --i) {
      auto na = add;
      int nxt = (bit - i) * 3 + 1;
      na[0] = 1;
      na[N] = -1;
      for (int j = 1 << (i + 1); j <= N; ++j) {
        na[j] = -1;
      }
      for (int j = (1 << i) - 1; j >= 1; --j) {
        na[j] = -2;
      }
      for (int j = 1 << i; j < min(N, (1 << (i + 1))); ++j) {
        na[j] = nxt;
      }
      later.push_back(na);
      na = add;
      for (int j = 2; j < N; ++j) {
        if (j >> i & 1) {
          if (i != 0) na[j] = nxt + 1;
          else na[j] = -2;
        } else {
          na[j] = nxt + 2;
        }
      }
      res.push_back(na);
      na = add;
      na[0] = 1;
      na[1] = -2;
      na[N] = -1;
      for (int j = 2; j < N; ++j) {
        if (j >> i & 1) {
          if (i != 0) na[j] = nxt + 3;
          else na[j] = -1;
        } else {
          na[j] = -2;
        }
      }
      res.push_back(na);
      na = add;
      na[0] = 1;
      na[1] = -2;
      na[N] = -1;
      for (int j = 2; j < N; ++j) {
        if (j >> i & 1) {
          na[j] = -1;
        } else {
          if (i != 0) na[j] = nxt + 3;
          else na[j] = -2;
        }
      }
      res.push_back(na);
    }
    int ptr = res.size();
    for (auto v : later) res.push_back(v);
    for (int i = 2; i < N; ++i) {
      for (int j = bit; j >= 0; --j) {
        if (i >> j & 1) {
          res[0][i] = ptr + bit - j;
          break;
        }
      }
    }
    // int _ =0;
    // for (auto& v : res) {
    //   cerr << _++ << " = ";
    //   for (auto& u : v) {
    //     cerr << u << " ";
    //   }
    //   cerr << "\n";
    // }
    // cerr << "\n";
    // cout << res.size() << "\n";
    return res;
}

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