Submission #635944

#	Time	Username	Problem	Language	Result	Execution time	Memory
635944		jakobrs	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1176 KiB

prison

#include "prison.h"

#include <cmath>
#include <vector>

static int digits, state_count;
struct State {
  int digit;
  int value;

  int variable() const { return digit % 2; }

  static State decode(int n) {
    n = state_count + 1 - n;
    State st;
    st.digit = n / 3;
    st.value = n % 3;

    if (n == 2) {
      st.value = 1;
    }
    return st;
  }
  int encode() const {
    if (digit == 0) {
      switch (value) {
      case 0:
        return -1;
      case 1:
        return 22;
      case 2:
        return -2;
      }
      return -3;
    } else {
      return state_count + 1 - (digit * 3 + value);
    }
  }
};

int log(int n, int b) {
  int res = 0;
  while (n > 0) {
    res += 1;
    n /= b;
  }
  res -= 1;
  return res;
}

int ipow(int b, int n) {
  int res = 1;
  while (n--)
    res *= b;
  return res;
}

int extract(int n, int digit) { return (n / ipow(3, digit)) % 3; }

std::vector<std::vector<int>> devise_strategy(int N) {
  digits = log(5000, 3) + 1;
  state_count = 23;
  std::vector<std::vector<int>> m(state_count);

  for (int i = 0; i < state_count; i++) {
    std::vector<int> &transitions = m[i];
    State st = State::decode(i);
    int var = st.variable();

    transitions.push_back(!var);
    for (int j = 1; j <= N; j++) {
      int here = extract(j, st.digit);
      if (st.value == here && st.digit > 0) {
        State to;
        to.digit = st.digit - 1;
        to.value = extract(j, to.digit);
        transitions.push_back(to.encode());
      } else if ((st.value > here) ^ var) {
        transitions.push_back(-2);
      } else {
        transitions.push_back(-1);
      }
    }
  }

  return m;
}

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