Submission #243528

#	Time	Username	Problem	Language	Result	Execution time	Memory
243528		AlexPop28	Cave (IOI13_cave)	C++11	100 / 100	906 ms	632 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

void exploreCave(int n) {
  auto Ask = [&](int state[]) {
    int ans = tryCombination(state);
    if (ans == -1) ans = n;
    return ans;
  };


  int *state = new int[n];
  int *door = new int[n];
  for (int i = 0; i < n; ++i) state[i] = 0, door[i] = -1;
  
  auto Flip = [&](int fin) {
    for (int i = 0; i <= fin; ++i)
      if (door[i] == -1) state[i] ^= 1;
  };
  
  for (int i = 0; i < n; ++i) {
    int pos = Ask(state);
    if (pos > i) {
      Flip(n - 1);
    }
    
    int lo = 0, hi = n - 1, ans = -1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      Flip(mid);
      pos = Ask(state);
      Flip(mid);
      
      if (pos > i) {
        ans = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    
    door[ans] = i;
    state[ans] ^= 1;
  }
  
  assert(tryCombination(state) == -1);
  
  answer(state, door);
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24