Advertisement
erek1e

IOI '13 P4 - Cave

Jun 27th, 2022
989
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include "cave.h"
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. void exploreCave(int N) {
  10.     int query[N] {};
  11.     set<int> indices;
  12.     for (int i = 0; i < N; ++i) indices.insert(i);
  13.  
  14.     int correctPos[N], door[N];
  15.  
  16.     // find switch of each door in order of doors
  17.     for (int d = 0; d < N; ++d) {
  18.         // find correct position of door
  19.         vector<int> v(indices.begin(), indices.end());
  20.         int n = N-d;
  21.         for (int i : v) query[i] = 0;
  22.         int correct = (tryCombination(query) == d ? 1 : 0);
  23.  
  24.         int left = 0, right = n;
  25.         while (right - left > 1) {
  26.             int mid = (left + right) / 2;
  27.             for (int i = left; i < mid; ++i) query[v[i]] = correct;
  28.             for (int i = mid; i < right; ++i) query[v[i]] = 1-correct;
  29.             if (tryCombination(query) == d) left = mid;
  30.             else right = mid;
  31.         }
  32.         door[v[left]] = d;
  33.         correctPos[v[left]] = correct;
  34.         indices.erase(v[left]);
  35.         query[v[left]] = correct;
  36.     }
  37.     answer(correctPos, door);
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement