Submission #1057109

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

prison

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

using namespace std;

#ifdef DEBUG 
  #include "/home/hp/contests/debug.h"
#else 
  #define debug(...) void(37)
#endif

vector<int> bases = {3, 3, 3, 3, 3, 3, 2};
constexpr int M = 21;
std::vector<std::vector<int>> devise_strategy(int N) {
  int s = int(bases.size());
  vector<int> size(s), car(s);
  {
    int cs = 5000;
    for (int i = 0; i < s; ++i) {
      cs -= 2;
      size[i] = (cs + bases[i] - 1) / (bases[i]);
      cs = (cs + bases[i] - 1) / bases[i];
      car[i] = cs;
    }
  }
  debug(size);
  vector<vector<int>> ans(M, vector<int>(N + 1));
  vector<int> mapping(N + 1);
  iota(mapping.begin(), mapping.end(), -2);
  ans[0][0] = 0;
  int LOWER = -2, UPPER = -3;
  for (int i = 1; i <= N; ++i) {
    if (i == 1) {
      ans[0][i] = -1;
      mapping[i] = LOWER;
    } else if (i == 5000) {
      ans[0][i] = -2;
      mapping[i] = UPPER;
    } else {
      ans[0][i] = 1 + mapping[i] / size[0];
    }
  }
  int start = 1;
  for (int i = 0; i < s; ++i) {
    vector<int> prev_digit(N + 1);
    for (int j = 1; j <= N; ++j) {
      if (mapping[j] < 0) {
        prev_digit[j] = -1;
      } else {
        prev_digit[j] = (mapping[j] / size[i]);
        int next = mapping[j] % size[i];
        if (next == 0) {
          mapping[j] = LOWER;
        } else if (next == size[i] - 1) {
          mapping[j] = UPPER;
        } else {
          mapping[j] = next - 1;
        }
      }
    }
    for (int j = 0; j < bases[i]; ++j) {
      int id = start + j;
      vector<int>& a = ans[id];
      a[0] = (i % 2 ? 0 : 1);
      for (int k = 1; k <= N; ++k) {
        if (prev_digit[k] != -1 && prev_digit[k] != j) {
          a[k] = -1 - ((prev_digit[k] > j) ^ a[0]);
        } else if (mapping[k] < 0) {
          a[k] = -1 - ((mapping[k] == UPPER) ^ a[0]);
        } else {
          assert(i != s - 1);
          int next = start + bases[i] + (mapping[k] / size[i + 1]);
          assert(next < M);
          a[k] = next;
        }
      }
    }
    start += bases[i];
  }
  return ans;
}

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