Submission #1008556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008556		somefjord	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	0 ms	348 KiB

prison

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

using namespace std;

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

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

int mapping[100];
int mapn = 1;

int packi(int pos, int b) { return ((pos + 1) << 1) | ((b & 1) << 0); }
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) {
  fill_n(mapping, 100, -1);
  mapping[0] = 0;

  int nbits = log2(N);
  int x = (nbits << 1) | 0b1;
  // printf("x = %d, nbits = %d\n", x, nbits);

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

  int maxi = 0;

  // pos -> previous pos
  for (int pos = nbits - 1; pos >= 0; --pos) {
    // b -> previously inspected bit
    for (int b = 0; b <= 1; ++b) {
      // IF we last checked A
      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;

      // v -> the current
      for (int v = 1; v <= N; ++v) {
        bool prevselfset = (v >> pos) & 1;
        if (prevselfset && !b) {
          s[i][v] = lasta ? -2 : -1;
        } else if (!prevselfset && b) {
          s[i][v] = lasta ? -1 : -2;
        } else if (pos > 0) {
          bool selfset = (v >> (pos - 1)) & 1;
          s[i][v] = pack(pos - 1, selfset);
        }
      }
    }
  }

  // whiteboard is always 0 initially
  s[0][0] = !(nbits % 2);
  for (int v = 1; v <= N; ++v) {
    bool selfset = (v >> (nbits - 1)) & 1;
    s[0][v] = pack(nbits - 1, selfset);
  }
  s.resize(maxi);
  // printf("maxi: %d\n", maxi);

  return s;
}

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