Submission #1202035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202035		bynix	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	7 ms	1096 KiB

prison

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

int b3(int n, int pos){
  for (int k = 0; k < pos - 1; k++) n /= 3;
  return n % 3;
}

int encode(int n, int pos){
  int d = b3(n, pos);
  pos -= 1 + (d == 2);
  return (d << 3) | pos;
}

pair<int, int> decode(int val){
  int d = val >> 3;
  int pos = (val & 7) + 1;
  pos += d == 2;
  return {d, pos};
}


vector<vector<int>> devise_strategy(int N){
  vector<vector<int>> strategy;
  for (int i = 0; i <= 22; i++) {
    vector<int> J(N + 1);
    if (i == 0){
      J[0] = 1;
      for (int j = 1; j <= N; j++) J[j] = encode(j, 8);
    } else {
      auto [p, pos] = decode(i);
      J[0] = pos & 1;
      for (int j = 1; j <= N; j++){
        int c = b3(j, pos);
        if (c < p) J[j] = -1 - pos % 2;
        else if (c > p) J[j] = pos % 2 - 2;
        else{
          J[j] = encode(j, pos - 1);
          if (pos == 2 && b3(j, 1) != 1) J[j] = ~((b3(j, 1) >> 1) ^ (pos % 2));
        }
      }
    }
    strategy.push_back(J);
  }
  return strategy;
}

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