Submission #1038664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038664		HappyCapybara	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	11 ms	1116 KiB

prison

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

vector<vector<int>> devise_strategy(int N){
  if (N == 2) return {{0, 1, 2}, {1, 0, -1}, {1, -2, 0}};
  int y = floor(log2(N))+1;
  vector<vector<int>> a(2*y-1, vector<int>(N+1));
  for (int i=0; i<2*(y-1)+1; i++){
    int g = ((i+1)/2) % 2;
    for (int j=0; j<N+1; j++){
      if (i == 0){
        if (j == 0){
          a[i][j] = 0;
          continue;
        }
        a[i][j] = min(1, (j&(1<<(y-1))))+1;
      }
      else {
        if (j == 0){
          a[i][j] = g;
          continue;
        }
        int b = min(1, j&(1<<(y-1-(i-1)/2)));
        if (b == 1 - i % 2){
          if (i < 2*y-3) a[i][j] = i+1+(i%2) + min(1, j&(1<<(y-2-(i-1)/2)));
          else {
            if (j & 1){
              if (g) a[i][j] = -1;
              else a[i][j] = -2;
            }
            else {
              if (g) a[i][j] = -2;
              else a[i][j] = -1;
            }
          }
        }
        else {
          if (b < 1-(i%2)){
            if (g) a[i][j] = -2;
            else a[i][j] = -1;
          }
          else {
            if (g) a[i][j] = -1;
            else a[i][j] = -2;
          }
        }
      }
    }
  }
  /*for (int i=0; i<2*y-1; i++){
    for (int j=0; j<N+1; j++) cout << a[i][j] << " ";
    cout << "\n";
  }*/
  return a;
}

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