Submission #630180

#	Time	Username	Problem	Language	Result	Execution time	Memory
630180		CyanForces	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	115 ms	1124 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) {
  cerr << "devise_strategy called with N = " << N << endl;

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

  vector<vi> strat(4, vi(N+1));
  auto [x, y] = dividers(1, N+1);

  strat[0][0] = 0;
  strat[0][1] = -1;
  strat[0][N] = -2;

  vi options({1,2,3});
  vector<pii> intervals(1,{1,N+1});
  int at = 4;

  rep(i,2,N) {
    int interval = (i >= x) + (i >= y);
    strat[0][i] = options[interval];
  }
  bool checkB = true;

  while(sz(intervals)) {
    //cerr << "new iteration" << endl;
    vector<pii> newIntervals;
    vi newOptions(3,-1);
    pii prev(-1,-1);
    for(auto[lo, hi] : intervals) {
      if (pii(lo, hi) == prev)
        continue;
      prev = pii(lo, hi);
      //cerr << lo << ", " << x << ", " << y << ", " << hi << endl;
      auto [x, y] = dividers(lo, hi);

      rep(prevInterval,0,3) {
        int prev = options[prevInterval];
        if (prev == -1)
          continue;
        while(prev >= sz(strat))
          strat.push_back(vi(N+1));
        strat[prev][0] = checkB;

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

          if (resp <= newLo) {
            strat[prev][resp] = -1-checkB;
            //cerr << "a" << endl;
            continue;
          }
          else if (resp >= newHi-1) {
            strat[prev][resp] = -1-(1-checkB);
            //cerr << "b" << endl;
            continue;
          }
          //cerr << "c" << endl;
          auto [newX, newY] = dividers(newLo, newHi);
          int nextInterval = (resp >= newX) + (resp >= newY);
          if (newOptions[nextInterval] == -1) {
            newOptions[nextInterval] = at++;
          }
          newIntervals.push_back({newLo, newHi});
          strat[prev][resp] = newOptions[nextInterval];
        }
      }
    }

    options = newOptions;
    checkB = !checkB;
    intervals = newIntervals;
  }

  /*
  rep(i,0,sz(strat)) {
    cerr << "x = " << i << endl;
    rep(j,0,N+1) {
      cerr << strat[i][j] << " ";
    }
    cerr << endl;
  }
  */
  return strat;
}

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