제출 #630148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630148		CyanForces	죄수들의 도전 (IOI22_prison)	C++17	10 / 100	18 ms	1620 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);

  strat[0][0] = 0;
  int mid = (N+2) / 2;
  rep(i,1,N+1) {
    strat[0][i] = 1 + (i >= mid);
  }

  function<void(int,int,int,bool)> dfs = [&](int p, int lo, int hi, bool checkB) {
    if (lo == hi-1)
      return;
    int a = p*2-3;
    int mid = (lo + hi) / 2;
    rep(prev,a,a+2) {
      if (strat.count(prev) == 0)
        strat[prev] = vi(N+1);
      int wasLowInterval = prev&1;
      strat[prev][0] = checkB;

      rep(resp,lo,hi) {
        int isLowInterval = resp < mid;
        if (wasLowInterval != isLowInterval) {
          // we know the answer
          if (wasLowInterval) {
            // the answer is in the opposite of what was opened
            strat[prev][resp] = -1-(1-checkB);
          }
          else {
            // the answer is in the current thing that was opened
            strat[prev][resp] = -1-checkB;
          }
          continue;
        }
        // A and B are in the same interval of length lenInterval
        if (lo == hi+1) {
          // impossible
          continue;
        }

        int newLo = isLowInterval ? lo : mid;
        int newHi = isLowInterval ? mid : hi;
        int newMid = (newLo + newHi) / 2;
        int isHiInterval = resp >= newMid;
        strat[prev][resp] = p*2-1 + isHiInterval;
      }
    }
    dfs(p+1, lo, mid, !checkB);
    dfs(p+1, mid, 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,maxX) {
    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: 0 / 90