Submission #626265

#	Time	Username	Problem	Language	Result	Execution time	Memory
626265		dariasc	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	14 ms	1776 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector

vec<int> ids;
vec<bool> processed;
map<int, vec<int>> arrs;
int bits = 12;

int get_terminate(int x) {
  if (x == 0) {
    return -1;
  }
  return -2;
}

void gen_last(int N, int id, int bag, bool on) {
  if (processed[id]) return;
  vec<int> arr(N+1, 0);
  for (int i = 1; i <= N; i++) {
    if (i & 1) {
      if (!on) {
        arr[i] = get_terminate(1 - bag);
      } else {
        arr[i] = get_terminate(bag);
      }
    } else {
      if (on) {
        arr[i] = get_terminate(bag);
      } else {
        arr[i] = get_terminate(1 - bag);
      }
    }
  }
  processed[id] = 1;
  arrs[id] = arr;
}

void gen(int N, int id, int next_on, int next_off, int bag, int bit, bool on) {
  if (processed[id]) {
    return;
  }
  vec<int> procedure(N+1, 0);
  procedure[0] = bag;
  for (int i = 1; i <= N; i++) {
    if ((1 << (bit+1)) & i) {
      // bit on
      if (on) {
        // continue
        procedure[i] = ((1 << (bit)) & i) ? next_on : next_off;
      } else {
        // terminate (other min)
        procedure[i] = get_terminate(1 - bag);
      }
    } else {
      // bit off
      if (on) {
        // terminate (this min)
        procedure[i] = get_terminate(bag);
      } else {
        // continue
        procedure[i] = ((1 << (bit)) & i) ? next_on : next_off;;
      }
    }
  }
  arrs[id] = procedure;
  processed[id] = 1;
  if (bit > 0) {
    int foward_on = ids.back(); ids.pop_back();
    int foward_off = ids.back(); ids.pop_back();
    gen(N, next_on, foward_on, foward_off, 1 - bag, bit - 1, 1);
    gen(N, next_off, foward_on, foward_off, 1 - bag, bit - 1, 0);
  }
  if (bit == 0) {
    gen_last(N, next_on, 1 - bag, 1);
    gen_last(N, next_off, 1 - bag, 0);
  }
}

std::vector<std::vector<int>> devise_strategy(int N) {
  ids.resize(500);
  processed.assign(500, 0);
  iota(ids.begin(), ids.end(), 0);
  reverse(ids.begin(), ids.end());
  ids.pop_back();
  int next_on = ids.back(); ids.pop_back();
  int next_off = ids.back(); ids.pop_back();
  vec<int> first(N+1, 0);
  for (int i = 1; i <= N; i++) {
    if ((1 << bits) & i) {
      first[i] = next_on;
    } else {
      first[i] = next_off;
    }
  }
  arrs[0] = first;
  processed[0] = 1;
  int foward_on = ids.back(); ids.pop_back();
  int foward_off = ids.back(); ids.pop_back();
  gen(N, next_on, foward_on, foward_off, 1, bits - 1, 1);
  gen(N, next_off, foward_on, foward_off, 1, bits - 1, 0);

  vec<vec<int>> procedure(arrs.size());
  for (auto [i, v] : arrs) {
    procedure[i] = v;
  }

  /*
  for (auto v : procedure) {
    for (int i = 0; i <= N; i++) {
      cout << v[i] << " ";
    }
    cout << endl;
  }
  */

  return procedure;
}

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