Submission #792293

#	Time	Username	Problem	Language	Result	Execution time	Memory
792293		MattTheNub	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	10 ms	1108 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
#include <vector>
using namespace std;

#ifdef EVAL
#define dbg2d(...)
#else
istream &__cin = cin;
#include "debug.h"
__cinwrapper __cin_wrapper;
#include "debug.cpp"
#endif

template <class T> using v = vector<T>;

v<v<int>> devise_strategy(int N) {
  v<v<int>> ans;
  ans.assign(25, v<int>(N + 1));

  ans[0][0] = 1;
  for (int j = 1; j <= N; j++) {
    if (j & (1 << 12)) {
      ans[0][j] = 1;
    } else {
      ans[0][j] = 2;
    }
  }
  for (int i = 1; i < 25; i++) {
    int cur = (~((i + 1) / 2) & 1);
    ans[i][0] = cur;
    int t = (i & 1) ? cur : (1 - cur);
    int b = (i & 1) ? 0 : 1;
    int k = 12 - (i - 1) / 2;

    cerr << i << " = " << k << (char)(t + 'A') << (char)(cur + 'A') << b
         << '\n';

    int n1 = i;
    if (n1 % 2 == 0)
      n1--;
    n1 += 2;

    t++;
    for (int j = 1; j <= N; j++) {
      if (((j >> k) & 1) == b) {
        ans[i][j] = -t;
      } else {
        if (k == 1) {
          ans[i][j] = (j & 1) ? -(1 - cur + 1) : -(cur + 1);
        } else {
          if (j & (1 << (k - 1))) {
            ans[i][j] = n1;
          } else {
            ans[i][j] = n1 + 1;
          }
        }
      }
    }
  }

  // ans[25][0] = 0;
  // for (int j = 1; j <= N; j++) {
  //   if (j & 1) {
  //     ans[25][j] = -2;
  //   } else {
  //     ans[25][j] = -1;
  //   }
  // }
  dbg2d(ans);

  return ans;
}

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