Submission #1203399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203399		HappyCapybara	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	7 ms	1924 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> s, idx;

vector<int> k = {3, 3, 3, 3, 3, 2, 2, 1, 1}, v = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7}, w = {1, 4, 7, 10, 13, 16, 18, 20};

void doidx(int l, int r, int d){
  if (d > 8) return;
  int step = (r-l-1)/k[d];
  idx[l][d] = -1;
  idx[r][d] = -2;
  assert(l+1+k[d]*step == r);
  for (int j=0; j<k[d]; j++){
    for (int i=0; i<step; i++) idx[l+1+j*step+i][d] = j;
    doidx(l+1+j*step, l+1+(j+1)*step-1, d+1);
  }
}

vector<vector<int>> devise_strategy(int N){
  s.resize(21, vector<int>(N+1, 0));
  idx.resize(5589, vector<int>(8, -3));
  doidx(1, 5588, 0);
  //for (int i=0; i<9; i++) cout << idx[10][i] << " " << idx[9][i] << " " << idx[32][i] << endl;
  s[0][0] = 0;
  s[0][1] = -1;
  for (int i=2; i<=N; i++) s[0][i] = idx[i][0]+1;
  for (int i=1; i<=20; i++){
    int d = v[i-1], val = i-w[d];
    s[i][0] = (d+1)%2;
    for (int j=1; j<=N; j++){
      if (idx[j][d] == -1) s[i][j] = -(s[i][0]+1);
      else if (idx[j][d] == -2) s[i][j] = s[i][0]-2;
      else if (idx[j][d] < val) s[i][j] = -(s[i][0]+1);
      else if (idx[j][d] > val) s[i][j] = s[i][0]-2;
      else {
        if (idx[j][d+1] == -1) s[i][j] = -(s[i][0]+1);
        else if (idx[j][d+1] == -2) s[i][j] = s[i][0]-2;
        else s[i][j] = w[d+1]+idx[j][d+1];
      }
    }
  }
  return s;
}

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