Submission #650468

#	Time	Username	Problem	Language	Result	Execution time	Memory
650468		NaimSS	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	14 ms	1236 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef vector<int> vi;
#define pb push_back

std::vector<std::vector<int>> devise_strategy(int N) {

  vector<vi> s;


  vi cur(N+1);
  cur[0]=0;

  int k = 1,pwr=0;
  while(k*2 <= N)k*=2,pwr++;

  // row 0:
  for(int i=1;i<=N;i++){
    // A tem i caras:
    if(i>>pwr&1){
      cur[i] = 2;
    }else cur[i]=1;
  }
  s.pb(cur);

  int box = 1;
  int posi=2;
  int mx = (pwr+1) * 2;
  while(pwr>=0){

    for(int it=0;it<2;it++){
      vi cur(N+1);

      cur[0] = box;
      for(int i=1;i<=N;i++){
        int have = i>>pwr&1;

        if(have && !it){
          cur[i] = -1-(box^1);
        }
        else if(!have && it){
          cur[i] = -1-box;
        }
        else{

          if(pwr == 0){
            cur[i] = -1; // should never happen
          }else{
            int haveNv = i>>(pwr-1)&1;
            if(haveNv)cur[i] = posi+2;
            else cur[i] = posi+1;
          }

        }



        if(cur[i]>mx)cur[i]=-1;
      }
      s.pb(cur);
    }

    posi+=2;
    box^=1;
    pwr--;  
  }

  return s;
}

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