Submission #794028

#	Time	Username	Problem	Language	Result	Execution time	Memory
794028		gesgha	Prisoner Challenge (IOI22_prison)	C++17	72 / 100	10 ms	1120 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
 
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
 
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ve = vector <T>;
 
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
 
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
 
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
 
const int oo = 1e9;
const ll OO = 1e18;
const int N = 2e5 + 100;
const int M = 5e3 + 100;
const int mod = 1e9 + 7;
const bool TEST = 1;



int nedobpw(int a, int n) {
  int x = 1;
  for (int i = 0; i < n; i++) {
    x *= a;
  }
  return x;
}

vector <vector<int>> devise_strategy(int N) {
  // freopen("log.txt", "w", stdout);
  ve <ve <int>> Z(24);
  int C = 0, POS = 1e9;
  for (int i = 0; i <= 24; i++) {
    int X = i / 3;
    int Y = i % 3;
    if (X == 0 && Y == 2) {
      C++;
      POS = i;
      continue;
    }
    Z[i - C].resize(N + 1);
    if (!X && !Y) Z[i - C][0] = 0;
    else if ((X & 1) == 0) Z[i - C][0] = 0;
    else Z[i - C][0] = 1;

    for (int j = 1; j <= N; j++) {
      int cnt = 0;
      if (X || Y) {
        cnt = X;
      } else {
        Z[i - C][j] = (j / nedobpw(3, 7)) % 3 + 3 * 7;
        continue;
      }
      int K = j;
      K /= nedobpw(3, cnt);
      if (K % 3 > Y) {
        if ((X&1) == 0) Z[i - C][j] = -2;
        else Z[i - C][j] = -1;
      } else if (K % 3 < Y) {
        if ((X&1) == 0) Z[i - C][j] = -1;
        else Z[i - C][j] = -2;
      } else {
        if (cnt == 0) {
          Z[i - C][j] = -1;
        } else {
          if(cnt == 1 && j % 3 == 0) {
            Z[i - C][j] = -1 - (X&1);
          } else if (cnt == 1 && j % 3 == 2) {
            Z[i - C][j] = -2 + (X&1);
          } else {
            Z[i - C][j] = ((j / nedobpw(3, cnt - 1)) % 3) + 3 * (cnt - 1);
          }
        }
      }
    }
  }
  for (int i = 0; i < sz(Z); i++) {
    for (int j = 0; j < sz(Z[i]); j++) {
      if(Z[i][j] > POS) Z[i][j]--;
    }
  }
  // fe (x, Z) {
  //   fe (y, x) {
  //     cout << y << " ";
  //   }
  //   cout << "\n";
  // }
  return Z;
}

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