Submission #1201970

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

prison

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

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

int encode(int number, int position){
  int digit = b3(number, position);
  position %= 8;
  if (position == 0) return ((digit + 1) << 3);
  else return (digit << 3) | position;
}

pair<int, int> decode(int val){
  int position = val & 7;
  int digit = (val >> 3) - (position == 0);
  position += 8 * (position == 0);
  return {digit, position};
}

vector<vector<int>> devise_strategy(int N){
  vector<vector<int>> strategy;
  for (int i = 0; i <= 24; 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);
      }
    }
    strategy.push_back(J);
  }
  return strategy;
}

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