Submission #626615

#	Time	Username	Problem	Language	Result	Execution time	Memory
626615		kdh9949	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	980 KiB

prison

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

constexpr int M[] = {2, 6, 20, 62, 188, 566, 1700, 5102};

vector<vector<int>> devise_strategy(int N) {
  vector<vector<int>> ans(21, vector<int>(M[7] + 1));

  ans[0][0] = 0;
  ans[0][1] = -1;
  ans[0][M[7]] = -2;
  for(int i = 2; i < M[7]; i++) ans[0][i] = 1 + (i - 2) / M[6];

  vector<int> chk(M[7] + 1);
  chk[1] = chk[M[7]] = 1;
  for(int t = 1, u = 6; t <= 16; t += 3, u--) {
    ans[t][0] = ans[t + 1][0] = ans[t + 2][0] = !ans[t - 1][0];
    for(int i = 1, j; ; i = j) {
      while(i < M[7] && chk[i]) i++;
      if(i == M[7]) break;
      for(j = i + 1; !chk[j]; j++);
      ans[t][i - 1] = ans[t + 1][i - 1] = ans[t + 2][i - 1] = -1 - ans[t][0];
      ans[t][j] = ans[t + 1][j] = ans[t + 2][j] = -2 + ans[t][0];
      for(int x = 0; x < 3; x++) {
        int S = i + x * M[u];
        int E = S + M[u];
        chk[S] = chk[E - 1] = 1;
        for(int y = 0; y < 3; y++) {
          if(x != y) fill(ans[t + y].begin() + S, ans[t + y].begin() + E, -1 - ((x > y) ^ ans[t][0]));
          else {
            ans[t + y][S] = -1 - ans[t][0];
            ans[t + y][E - 1] = -2 + ans[t][0];
            for(int z = S + 1; z < E - 1; z++) ans[t + y][z] = t + 3 + (z - S - 1) / M[u - 1];
          }
        }
      }
    }
  }

  ans[19][0] = ans[20][0] = !ans[18][0];
  for(int i = 1, j; ; i = j) {
    while(i < M[7] && chk[i]) i++;
    if(i == M[7]) break;
    for(j = i + 1; !chk[j]; j++);
    for(int k = i - 1; k <= j; k++) {
      ans[19][k] = -1 - (k <= i);
      ans[20][k] = -1 - (k < j - 1);
    }
  }

  for(int i = 0; i <= 20; i++) ans[i].resize(N + 1);

  return ans;
}

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