Submission #630161

#	Time	Username	Problem	Language	Result	Execution time	Memory
630161		CyanForces	Prisoner Challenge (IOI22_prison)	C++17	Compilation error	0 ms	0 KiB

prison

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;
}

Compilation message (stderr)

prison.cpp:1:1: error: 'vector' does not name a type
    1 | vector<vi> devise_strategy(int N) {
      | ^~~~~~