Advertisement
mickypinata

IOI13: Cave

Jul 21st, 2021
1,007
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool isOpen(int i, int ret){
  5.     return ret == -1 || ret > i;
  6. }
  7.  
  8. void exploreCave(int N){
  9.     int switches[N], permu[N], ansD[N], ansP[N];
  10.     for(int i = 0; i < N; ++i){
  11.         switches[i] = i;
  12.         permu[i] = 0;
  13.         ansP[i] = 0;
  14.         ansD[i] = 0;
  15.     }
  16.     for(int i = 0; i < N; ++i){
  17.         for(int j = 0; j < N - i; ++j){
  18.             permu[switches[j]] = 0;
  19.         }
  20.         int correct;
  21.         if(isOpen(i, tryCombination(permu))){
  22.             correct = 0;
  23.         } else {
  24.             correct = 1;
  25.         }
  26.         int l = 0;
  27.         int r = N - i - 1;
  28.         while(l < r){
  29.             int m = (l + r) / 2;
  30.             for(int j = l; j <= m; ++j){
  31.                 permu[switches[j]] = correct;
  32.             }
  33.             for(int j = m + 1; j <= r; ++j){
  34.                 permu[switches[j]] = correct ^ 1;
  35.             }
  36.             if(isOpen(i, tryCombination(permu))){
  37.                 r = m;
  38.             } else {
  39.                 for(int j = l; j <= m; ++j){
  40.                     permu[switches[j]] = correct ^ 1;
  41.                 }
  42.                 l = m + 1;
  43.             }
  44.         }
  45.         ansP[switches[l]] = correct;
  46.         permu[switches[l]] = correct;
  47.         ansD[switches[l]] = i;
  48.         swap(switches[l], switches[N - i - 1]);
  49.     }
  50.     answer(ansP, ansD);
  51. }
  52.  
Advertisement
RAW Paste Data Copied
Advertisement