Submission #1248001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248001		madamadam3	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	12 ms	1096 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)
#define p3(p) int(pow(3, p))

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

const int STATES = 25;

int transition(int current, int bagValue) {
  if (current == 0) {
    return trit(bagValue, 7) + 1;
  } else if (current == 21) {
    if (trit(bagValue, 1) < 2) return -2;
    if (trit(bagValue, 0) == 1) return 22;
    return trit(bagValue, 0) == 2 ? -1 : -2;
  } else if (current == 20) {
    if (trit(bagValue, 1) > 1) return -1;
    else if (trit(bagValue, 1) < 1) return -2;
    if (trit(bagValue, 0) == 1) return 22;
    return trit(bagValue, 0) == 2 ? -1 : -2;
  } else if (current == 19) {
    if (trit(bagValue, 1) > 0) return -1;
    if (trit(bagValue, 0) == 1) return 22;
    return trit(bagValue, 0) == 2 ? -1 : -2;
  }
  else if (current == 22) {
    return trit(bagValue, 0) > 1 ? -2 : -1;
  } else if (current == 24) {
    return -1;
  } else if (current == 23) {
    return trit(bagValue, 0) > 1 ? -2 : -1;
  }
  // 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 = 8 - ((current + 2) / 3);
  int pos = (current - 1) % 3;
  bool isa = bit % 2 == 0;
  if (bit < 0) return -1;

  if (trit(bagValue, bit) == pos) {
    // cout << "cold: " << current << " cbit: " << bit << "\n";
    current = ((8 - bit) - 1) * 3 + 1;
    // cout << current << "\n";
    int toret = -1;

    if (trit(bagValue, bit - 1) == 0) toret = current + 3;
    if (trit(bagValue, bit - 1) == 1) toret = current + 4;
    if (trit(bagValue, bit - 1) == 2) toret = current + 5;

    if (toret >= 22) toret = 22;
    return toret;
  } else {
    if (isa) {
      return trit(bagValue, bit) > pos ? -2 : -1;
    } else {
      return trit(bagValue, bit) > pos ? -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));

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

    for (int j = 1; j <= N; j++) {
      s[i][j] = transition(i, j);
      if (s[i][j] < -2 || s[i][j] >= STATES) s[i][j] = -1;
    }
  }

  // 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: 55 / 90