Submission #1008827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008827		somefjord	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	8 ms	1116 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; }
/*
int pack(int pos, int b) {
  int p = packi(pos, b);
  if (mapping[p] != -1)
    return mapping[p];
  mapping[p] = mapn;
  return mapn++;
}*/

vector<vector<int>> devise_strategy(int N) {
  int nbits = 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, lasta = 0
      auto lasta = (pos % 2);

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

      // IF we last checked A -> check B next, and vice-versa
      s[i][0] = !lasta;

      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
      for (int v = 1; v <= N; ++v) {
        bool prevselfset = (v >> bitpos) & 1;
        if (prevselfset && !b) {
          s[i][v] = lasta ? -2 : -1;
        } else if (!prevselfset && b) {
          s[i][v] = lasta ? -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] = lasta ? -2 : -1;
          } else {
            s[i][v] = lasta ? -1 : -2;
          }
        }

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

  if (DEBUG > 1)
    printf("---\n");

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

    s[0][v] = pack(0, selfset);

    if (DEBUG > 2)
      printf("  s[%d][%d] = %d\n", 0, v, s[0][v]);
  }
  // If the value is 1, then it's the least
  s[0][1] = -1;
  // vice-versa
  s[0][N] = -2;
  if (DEBUG)
    printf("maxi: %d\n", maxi);

  return s;
}

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