Submission #1008409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008409		somefjord	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	22 ms	2140 KiB

prison

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

using namespace std;

int log2(int v) {
  int r = 0;

  while (v >>= 1) {
    r++;
  }
  return r + 1;
}

int pack(int pos, int b, int ab) {
  return ((pos + 1) << 2) | ((b & 1) << 1) | ((ab & 1) << 0);
}

vector<vector<int>> devise_strategy(int N) {
  int nbits = log2(N);
  int x = (nbits << 2) | 0b11;
  // printf("x = %d, nbits = %d\n", x, nbits);

  vector<vector<int>> s(x + 1, vector<int>(N + 1));

  for (int pos = nbits - 1; pos >= 0; --pos) {
    // previously inspected bit
    for (int b = 0; b <= 1; ++b) {
      // ab = 0 => bag a
      // ab = 1 => bag b
      // previously inspected
      for (int ab = 0; ab <= 1; ++ab) {
        int i = pack(pos, b, ab);

        // Inspect the other bag next
        s[i][0] = !ab;

        for (int v = 1; v <= N; ++v) {
          // printf("pos: %d b: %d ab: %d v: %d\n", pos, b, ab, v);

          // If this is B -> we have checked A at the same bit
          if (!ab) {
            bool selfset = (v >> pos) & 1;
            if (selfset && !b) {
              // if the bag we previously inspected did not have bit at pos set,
              // but we do
              s[i][v] = -1;
            } else if (!selfset && b) {
              // vice-versa
              s[i][v] = -2;
            } else if (pos != 0) {
              // Move to a lesser significant bit. Say we are at B.
              s[i][v] = pack(pos, 0 /* don't care */, 1);
            } else {
              // how?
            }
          } else if (pos != 0) {
            bool selfset = (v >> (pos - 1)) & 1;

            // We were at B, so move to A. We check at push to whiteboard
            s[i][v] = pack(pos - 1, selfset, 0);
          }
          // printf("  s[%d][%d] = %d\n", i, v, s[i][v]);
        }
      }
    }
  }

  // whiteboard is always 0 initially, so inspect A
  s[0][0] = 0;
  for (int v = 1; v <= N; ++v) {
    bool selfset = (v >> (nbits - 1)) & 1;
    s[0][v] = pack(nbits - 1, selfset, 0);
  }

  return s;
}

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