Submission #1009705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009705		somefjord	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	6 ms	604 KiB

prison

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

using namespace std;

constexpr int DEBUG = 0;

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

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

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

vector<vector<int>> devise_strategy(int N) {
  int nbits = 13; // log2(N);
  int x = ((nbits - 1) << 1) | 0b1;

  if (DEBUG)
    printf("nbits: %d, x: %d\n", nbits, x);

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

  int maxi = 0;

  // pos -> previous pos
  for (int pos = 0; pos < nbits - 1; ++pos) {
    int bitpos = nbits - 1 - pos;

    // b -> previously inspected bit
    for (int b = 0; b <= 1; ++b) {
      // IF we last checked A, lastab = 0
      auto lastab = (pos % 2);

      int i = pack(pos, b);
      maxi = max(i, maxi);

      // IF we last checked A -> check B next, and vice-versa
      if (pos == 1)
        // We know that the MSB of the previous check (A) is 0. This state
        // won't be reached if the MSB of the previous check (A) is 1. We should
        // then inspect B.
        s[i][0] = lastab;
      else
        s[i][0] = !lastab;

      if (DEBUG > 1)
        printf("[%d] prev pos: %d, prev bitpos: %d, prev b: %d -> check: %d\n",
               i, pos, bitpos, b, s[i][0]);

      // v -> the current value
      for (int v = 1; v <= N; ++v) {
        bool prevselfset = (v >> bitpos) & 1;

        if (pos == 0 && b && prevselfset) {
          // If we're from the MSB of the previous check (A) and the MSB of the
          // current check (B) are both 1, this means that the 2 following bits
          // to the right MUST be 0
          s[i][v] = pack(pos + 2, 0);
        } else if (pos == 1 && (v >> (nbits - 1)) & 1) {
          // We know that the MSB of the previous check (A) is 0. This state
          // won't be reached if the MSB of the previous check (A) is 1.
          // if the MSB of B is 1, then we know that A is smaller
          s[i][v] = -1;
          // Otherwise, continue
        } else if (prevselfset && !b) {
          s[i][v] = lastab ? -2 : -1;
        } else if (!prevselfset && b) {
          s[i][v] = lastab ? -1 : -2;
        } else if (bitpos > 1) {
          bool selfset = (v >> (bitpos - 1)) & 1;
          s[i][v] = pack(pos + 1, selfset);
        } else {
          bool selfset = v & 1;
          if (selfset) {
            s[i][v] = lastab ? -2 : -1;
          } else {
            s[i][v] = lastab ? -1 : -2;
          }
        }

        if (DEBUG > 2)
          printf("  s[%d][%d] = %d\n", i, v, s[i][v]);
      }
    }
  }

  // whiteboard is always 0 initially
  bool startab = 0;
  s[0][0] = startab;
  for (int v = 1; v <= N; ++v) {
    bool selfset = (v >> (nbits - 1)) & 1;

    if (selfset)
      s[0][v] = pack(0, selfset);
    else
      s[0][v] = pack(1, 0);
  }

  // If the value is 1, then it's the least
  s[0][1] = -1;
  // vice-versa
  s[0][N] = -2;

  if (DEBUG > 1) {
    vector<bool> visited(x, false);
    for (int i = 0; i < x; ++i) {
      for (int v = 1; v <= N; ++v) {
        if (DEBUG > 2)
          printf("%d %d\n", i, s[i][v]);
        if (s[i][v] >= 0)
          visited[s[i][v]] = true;
      }
    }
    for (int i = 1; i < x; ++i) {
      if (!visited[i])
        printf("[!] Unvisited: %d\n", i);
    }
  }

  if (DEBUG)
    printf("maxi: %d\n", maxi);

  return s;
}

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