Submission #630162

#	Time	Username	Problem	Language	Result	Execution time	Memory
630162		CyanForces	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	292 ms	1972 KiB

prison

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<vi> devise_strategy(int N) {
  map<int, vi> strat;
  strat[0] = vi(N+1);

  auto dividers = [&](int lo, int hi) {
    int stepSize = (hi - lo) / 3;
    int x = lo + stepSize;
    stepSize = (hi - x) / 2;
    return pii(x, x + stepSize);
  };

  strat[0][0] = 0;
  auto [x, y] = dividers(1, N+1);
  rep(i,1,N+1) {
    if (i < x) {
      strat[0][i] = 1;
    }
    else if (i < y) {
      strat[0][i] = 2;
    }
    else {
      strat[0][i] = 3;
    }
  }
  strat[0][1] = -1;
  strat[0][N] = -2;

  function<void(int,int,int,bool)> dfs = [&](int p, int lo, int hi, bool checkB) {
    int num = hi - lo;
    if (num <= 1) {
      return;
    }
    auto [x, y] = dividers(lo, hi);
    int a = p*3-5;
    rep(prev,a,a+3) {
      if (strat.count(prev) == 0)
        strat[prev] = vi(N+1);
      int prevInterval = (prev - 1) % 3;
      strat[prev][0] = checkB;

      rep(resp,lo,hi) {
        int newInterval = (resp >= x) + (resp >= y);
        if (newInterval > prevInterval || resp == hi-1) {
          // the answer is in the opposite of what was opened
          strat[prev][resp] = -1-(1-checkB);
          continue;
        }
        else if (newInterval < prevInterval || resp == lo) {
          // the answer is in the current thing that was opened
          strat[prev][resp] = -1-checkB;
          continue;
        }
        // A and B are in the same interval

        int newLo = vi({lo, x, y})[newInterval];
        int newHi = vi({x, y, hi})[newInterval];
        auto [newX, newY] = dividers(newLo, newHi);
        int nextInterval = (resp >= newX) + (resp >= newY);
        strat[prev][resp] = p*3-2 + nextInterval;
      }
    }
    dfs(p+1, lo, x, !checkB);
    dfs(p+1, x, y, !checkB);
    dfs(p+1, y, hi, !checkB);
  };
  dfs(2, 1, N+1, true);

  vector<vi> retvalue(rbegin(strat)->first + 1, vi(N+1));
  trav(p, strat) {
    retvalue[p.first] = p.second;
  }
  rep(i,0,sz(retvalue)) {
    cerr << "x = " << i << endl;
    rep(j,0,N+1) {
      cerr << strat[i][j] << " ";
    }
    cerr << endl;
  }
  //retvalue.resize(min(sz(retvalue), 26));
  rep(p,0,sz(retvalue))
    trav(elem,retvalue[p]) elem = min(elem, sz(retvalue)-1);
  return retvalue;
}

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