Submission #1247971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247971		madamadam3	Prisoner Challenge (IOI22_prison)	C++20	51.50 / 100	9 ms	1348 KiB

prison

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

using namespace std;

#define bv(x, i) (((x) & (1 << (i))) ? 1 : 0)
#define trit(x, i) (((x) / static_cast<int>(std::pow(3, (i)))) % 3)

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

struct State {
  int bitID, id, bag;
  // 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, BASE = 2, STATES = 30;
vector<State> states;
int stateID[BITS][BASE];

// void build_state_table() {
//   for (int i = BITS - 1; i >= 0; i--) {
//     for (auto state : {0, 1, 2}) {
//       stateID[i][state] = (int) states.size();
//       states.push_back(State {i, state, i % 2});
//     }
//   }
// }

int transition(int current, int bagValue) {
  if (current == 0) {
    return bagValue & (1 << 12) ? 1 : 2;
  } else if (current == 24) {
    if (bagValue & (1 << 1)) return -2;
    return bagValue & (1 << 0) ? -2 : -1;
  } else if (current == 23) {
    if (bagValue & (1 << 1)) return bagValue & (1 << 0) ? -2 : -1;
    return -1;
  }

  int bit = 13 - ((current + 1) / 2);
  bool pos = current % 2 == 1;
  bool isa = bit % 2 == 1;
  if (bit < 0) return -1;

  if (((bagValue & (1 << bit)) > 0) == pos) {
    if (current % 2 == 0) current--;
    return current + ((bagValue & (1 << (bit - 1))) ? 2 : 3);
  } else {
    if (isa) {
      return bagValue & (1 << bit) ? -2 : -1;
    } else {
      return bagValue & (1 << bit) ? -1 : -2;
    }
  }

  return -1;
}

vi used(32, 0);

int test_strategy(int a, int b, vvi &strategy) {
  int cnum = 0;
  for (int i = 0; i < 500; i++) {
    used[cnum]++;
    int choose = strategy[cnum][0];
    if (strategy[cnum][choose ? b : a] < 0) {
      return -strategy[cnum][choose ? b : a];
    } else {
      cnum = strategy[cnum][choose ? b : a];
    }
  }
  
  return 0;
}

vvi devise_strategy(int N) {
  vvi s(STATES, vi(N+1, 0));
  // build_state_table();

  for (int i = 0; i < STATES; i++) {
    // State cur = states[i];
    int bit = 13 - ((i + 1) / 2);
    s[i][0] = bit % 2 == 1 ? 0 : 1;
    // s[i][0] = min(i, 1);

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

  // test_strategy(4096, 5000, s);
  // for (int i = 1; i <= 5000; i++) {
  //   for (int j = 1; j <= 5000; j++) {
  //     if (i == j) continue;
  //     int ans = test_strategy(i, j, s);

  //     if (ans != (i < j ? 1 : 2)) {
  //       cout << "Fails on: " << i << ", " << j << "\n";
  //       break;  
  //     }
  //   }
  // }

  // vi bits(STATES); iota(bits.begin(), bits.end(), 0);
  // sort(bits.begin(), bits.end(), [&](const auto &a, const auto &b) {return used[a] < used[b];});
  // for (int i = 0; i < STATES; i++) {
  //   cout << "Used state " << bits[i] << " " << used[bits[i]] << " times\n";
  // }

  // int mstate = 0; for (int i = 0; i < used.size(); i++) if (used[i] > 0) mstate = i;
  // double score = 10.0F;
  // if (40 <= mstate && mstate <= 60) {
  //   score += 20;
  // } else if (26 <= mstate && mstate <= 39) {
  //   score += 25 + 1.5 * (40 - mstate);
  // } else if (24 <= mstate && mstate <= 25) {
  //   score += 50 + 5 * (25 - mstate);
  // } else if (mstate == 23) {
  //   score += 62;
  // } else {
  //   score += 70 + 10 * (22 - mstate);
  // }

  // cout << "Max X: " << mstate << " Solution scores: " << score << " / 100\n";
  return s;
}

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