Submission #630121

#	Time	Username	Problem	Language	Result	Execution time	Memory
630121		CyanForces	Prisoner Challenge (IOI22_prison)	C++17	44 / 100	24 ms	1404 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) {
  int maxX = 35;
  vector<vi> retvalue(maxX, vi(N+1));

  bool checkB = true;
  int lenInterval = 4096;

  retvalue[0][0] = 0;
  rep(i,1,N+1) {
    retvalue[0][i] = 1 + i / lenInterval;
  }
  int p = 2;
  while(lenInterval) {
    rep(prev,p*2-3,p*2-1) {
      int wasLowInterval = prev&1;
      retvalue[prev][0] = checkB;
      rep(resp,1,N+1) {
        int temp = resp % (2*lenInterval);
        int isLowInterval = temp < lenInterval;
        if (wasLowInterval != isLowInterval) {
          // we know the answer
          if (wasLowInterval) {
            // the answer is in the opposite of what was opened
            retvalue[prev][resp] = -1-(1-checkB);
          }
          else {
            // the answer is in the current thing that was opened
            retvalue[prev][resp] = -1-checkB;
          }
          continue;
        }
        if (lenInterval == 1) {
          // can only happen if they are the same number which is never the case
          continue;
        }
        temp = resp % lenInterval;
        int newIntervalLen = lenInterval / 2;
        int isHiInterval = temp >= newIntervalLen;
        retvalue[prev][resp] = p*2-1 + isHiInterval;
      }
    }

    p++;
    lenInterval /= 2;
    checkB = !checkB;
  }
  /*rep(i,0,maxX) {
    cerr << "x = " << i << endl;
    rep(j,0,N+1) {
      cerr << retvalue[i][j] << " ";
    }
    cerr << endl;
  }*/
  return retvalue;
}

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