Submission #1181818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181818		madamadam3	Prisoner Challenge (IOI22_prison)	C++20	38 / 100	11 ms	1608 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

#define bv(x, i) (((x) & (1 << (i))) ? 1 : 0)

using vi = vector<int>;
using vvi = vector<vi>;

struct State {
  int bitID, id;
  // if id = 0, then current bag is A
  // if id = 1, then current bag is B, and A[bit] = 0
  // if id = 2, then current bag is B, and A[bit] = 1
};

const int BITS = 13;
vector<State> states;
int stateID[BITS][3];

void build_state_table() {
  for (int i = BITS - 1; i >= 0; i--) {
    for (int state = 0; state < 3; state++) {
      stateID[i][state] = (int) states.size();
      states.push_back(State {i, state});
    }
  }
}

int transition(State current, int bagValue) {
  State newState = current;
  if (current.id == 0) {
    newState.id = 1 + bv(bagValue, current.bitID);
    newState.bitID = current.bitID;
  } else {
    if (current.id - 1 != bv(bagValue, current.bitID)) {
      return bv(bagValue, current.bitID) == 1 ? -1 : -2;
    } else {
      newState.id = 0;
      newState.bitID = current.bitID - 1;
      if (newState.bitID < 0) return -1; // shouldnt happen
    }
  }

  return stateID[newState.bitID][newState.id];
}

vvi devise_strategy(int N) {
  vvi s(BITS * 3, vi(N+1, 0));
  build_state_table();

  for (int i = 0; i < BITS * 3; i++) {
    State cur = states[i];
    s[i][0] = cur.id == 0 ? 0 : 1;

    for (int j = 1; j <= N; j++) {
      s[i][j] = transition(cur, j);
    }
  }
  return s;
}

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