Submission #1140346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140346		Maaxle	Prisoner Challenge (IOI22_prison)	C++20	48.50 / 100	26 ms	1352 KiB

prison

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

#define range(it, a, b) for (ll it = a; it < b; it++)
#define invr(it, a, b) for (ll it = a; it >= b; it--)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define ld long double
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>
#define v(x) vector<x>

using namespace std;

string to_base3 (int x) {
  string ans = "";
  int pow = 2187;

  invr(i, 7, 0) {
    if (x >= 2*pow) {
      ans += '2';
      x -= 2*pow; 
      pow /= 3;
      continue;
    }

    if (x >= pow) {
      ans += '1';
      x -= pow;
      pow /= 3;
      continue;
    }

    ans += '0';
    pow /= 3;
  } 
  return ans;
}

v(v(int)) devise_strategy(int N) {
  v(v(int)) ans (32, v(int)(N+1));

  range(b, 0, 8) {
    range(s, 0, 4) {
      range(j, 1, N+1) {
        int i = (s << 3) + b;
        ans[i][0] = (s > 0);

        string j3 = to_base3(j);
        // cout << j3 << ' ';

        // A IS ALREADY CHECKED
        if (s > 0) {
          int bb = (j3[b] - '0');
          int ab = s - 1;

          if (ab != bb) 
            ans[i][j] = (ab < bb ? -1 : -2);
          else ans[i][j] = b+1;
          continue;
        }
        
        // CHECK A
        int ab = (j3[b] - '0');
        ans[i][j] = ((ab+1) << 3) + b;
      }
    }
  }

  return ans;
}

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