Submission #657013

#	Time	Username	Problem	Language	Result	Execution time	Memory
657013		lumibons	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1000 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

pair<int, int> reduce(int v, int t) {
  // cerr << "reducing " << v << " by " << t << ": ";
  v--;
  int h = 3 * 3 * 3 * 3 * 3 * 22, a;
  for (int i = 0; i < min(t, 5); i++) {
    h /= 3;
    v %= h;
  }
  if (t < 5)
    a = v / (h / 3);
  for (int i = 0; i < min(t - 5, 2); i++) {
    if (v == 0 || v == h - 1)
      return {v, v == 0 ? -1 : -2};
    v--;
    h -= 2;
    h /= 2;
    v %= h;
  }
  if (t >= 5 && t < 7)
    a = v == 0 ? -1 : (v == h - 1 ? -2 : (v - 1) / ((h - 2) / 2));
  if (t == 7)
    a = v == 0 ? -1 : (v == h - 1 ? -2 : 0);
  if (t > 7) {
    if (v == 0 || v == h - 1)
      return {v, v == 0 ? -1 : -2};
    v--;
    h -= 2;
    a = v == 0 ? -1 : -2;
  }
  // cerr << v << " " << a << " " << h << "\n";
  return {v, a};
}

tuple<int, int, int> pile(int x) {
  int p = 0;
  int i = 0, j = 0;
  if (x)
    p ^= 1, j++;
  for (i = 0; i < 5 && x > 3; i++, x -= 3, j++)
    p ^= 1;
  if (i == 5) {
    for (i = 0; i < 2 && x > 2; i++, x -= 2, j++)
      p ^= 1;
    if (i == 2 && x > 1)
      i = 0, j++, x--, p ^= 1;
  }
  return {p, x, j};
}

int undo(int x, int t) {
  for (int i = 0; i < min(5, t); i++)
    x += 3;
  for (int i = 5; i < min(7, t); i++)
    x += 2;
  if (t == 8)
    x++;
  return x;
}

int action(int x, int v) {
  if (x == 0) {
    auto [nv, a] = reduce(v, 0);
    if (a < 0)
      return a;
    return a + 1;
  }
  auto [p, nx, t] = pile(x);
  auto [nv, a] = reduce(v, t - 1);
  if (a < 0)
    return a ^ p;
  if (a + 1 != nx)
    return (a + 1 < nx ? -1 : -2) ^ p;
  auto [nnv, na] = reduce(v, t);
  if (na < 0)
    return na ^ p;
  return undo(na + 1, t);
}

std::vector<std::vector<int>> devise_strategy(int N) {
  vector<vector<int>> s(21, vector<int>(N + 1));
  for (int x = 0; x < 21; x++) {
    auto [p, nx, t] = pile(x);
    s[x][0] = p;
    for (int v = 1; v <= N; v++)
      s[x][v] = action(x, v);
  }
  return s;
}

Compilation message (stderr)

prison.cpp: In function 'std::pair<int, int> reduce(int, int)':
prison.cpp:40:15: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |   return {v, a};
      |               ^

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