Submission #1223281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223281		brinton	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	7 ms	1096 KiB

prison

#include "prison.h"

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

vector<vector<int>> devise_strategy(int N) {
  int k = __lg(N);
  int m = 2*k;
  vector<vector<int>> ans(m+1,vector<int>(N+1));
  
  for(int see = 0;see <= m;see++){
    int current_bit = (see+1)/2;
    int nxt_bit = current_bit-1;
    if(nxt_bit < 0) nxt_bit = k;
    
    ans[see][0] = (k-nxt_bit)%2;// current looking at 0:A,1:B
    for(int bag = 1;bag <= N;bag++){
      int nv = ((1 << nxt_bit)&bag)!=0;
      int cv = ((1 << current_bit)&bag)!=0;
      if(see == 0){
        ans[see][bag] = 2*nxt_bit-nv;
        continue;
      }
      if(see%2 != cv){
        // got the answer;
        if((cv > see%2) == ans[see][0]){
          ans[see][bag] = -1;
        }else{
          ans[see][bag] = -2;
        }
      }else if(see <= 2){
        // must have the answer;
        if((bag&1) == ans[see][0]){
          ans[see][bag] = -1;
        }else{
          ans[see][bag] = -2;
        }
      }else{
        ans[see][bag] = 2*nxt_bit-nv;
      }
    }
  }
  return ans;
}

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