Submission #814319

#	Time	Username	Problem	Language	Result	Execution time	Memory
814319		KoD	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	1348 KiB

prison

#include "prison.h"
#include <utility>
#include <vector>
#include <iostream>
using namespace std;

namespace kod {

constexpr int N = 5102;
constexpr int M = 21;
constexpr int D = 6;
constexpr int len[] = {2, 6, 20, 62, 188, 566, 1700, 5102};
int S[M][N + 1];

void build() {
  {
    S[0][0] = 0;
    S[0][1] = -1;
    S[0][N] = -2;
    for (int i = 2; i <= N - 1; ++i) {
      S[0][i] = 3 * D + (i - 2) / len[D];
    }
  }
  for (int d = D; d >= 0; --d) {
    const char c = (d % 2 == 1 ? 'A' : 'B');
    for (int k = (d == 0); k < 3; ++k) {
      const int u = 3 * d + k;
      S[u][0] = (c == 'A' ? 0 : 1);
      for (int i = 1; i <= N; ++i) {
        S[u][i] = [&] {
          int x = 0, y = i;
          for (int j = D; j > d; --j) {
            x = (y - 2) / len[j];
            y = (y - 2) % len[j] + 1;
          }
          if (y == 1) {
            return c == 'A' ? -1 : -2;
          } else if (y == len[d + 1]) {
            return c == 'A' ? -2 : -1;
          } else {
            x = (y - 2) / len[d] + (d == 0);
            y = (y - 2) % len[d] + 1;
          }
          if (x < k) {
            return c == 'A' ? -1 : -2;
          } else if (x > k) {
            return c == 'A' ? -2 : -1;
          } else {
            if (y == 1) {
              return c == 'A' ? -1 : -2;
            } else if (y == len[d]) {
              return c == 'A' ? -2 : -1;
            } else {
              return 3 * (d - 1) + (y - 2) / len[d - 1] + (d == 1);
            }
          }
        }();
      }
    }
  }
}

}  // namespace kod

vector<vector<int>> devise_strategy(int N) {
  kod::build();
  vector S(kod::M, vector(N + 1, 0));
  for (int i = 0; i < kod::M; ++i) {
    for (int j = 0; j <= N; ++j) {
      S[i][j] = kod::S[i][j];
    }
  }
  return S;
}

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