---
tags: IOI
---
# IOI2013 Day2-1 Cave

インタラクティブの典型 "二分法"

## 問題文

http://www.ioi2013.org/wp-content/uploads/tasks/day2/cave/cave%20-%20JPN%20(ja).pdf
https://oj.uz/problem/view/IOI13_cave

洞窟の行く先を $N$ 個のドアが阻んでいます。
$N$ 個のスイッチがあり、それぞれが1つのドアに繋がっています。
どのスイッチがどのドアと繋がっているか、スイッチをどちらに倒すとドアが開くかはわかりません。
70000 回クエリを送ることができ、スイッチの倒しかたを送ると、どこまでドアに阻まれずに進めるかがわかります。
どのスイッチがどのドアと繋がっているかと、ドアを開けるためのスイッチの倒し方を明らかにしてください。

$1 ≤ N ≤ 5000$

## 考察

二分法かな？
$5000 \cdot \log_25000 = 61439$
二分法だった。

## 実装

うまく関数に切り分けよう

https://oj.uz/submission/210381

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
using uint = unsigned;
#define rep(n) for(int i = 0; i < n; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
 
 
int n;
int s[5000], d[5000];
int flag, x;
vector<int> candidate;
bool query(){
    uint a = tryCombination(s);
    return a > x;
}
auto find(vector<int>::iterator begin, vector<int>::iterator end){
    if(end - begin == 1) return begin;
    auto cen = begin + (end - begin) / 2;
    for(auto p = begin; p < cen; p++) s[*p] = flag;
    for(auto p = cen; p < end; p++) s[*p] = !flag;
    if(query()) return find(begin, cen);
    else return find(cen, end);
}
void find(int _x){
    x = _x;
    each(i, candidate) s[i] = 1;
    flag = query();
    auto p = find(all(candidate));
    d[*p] = x;
    s[*p] = flag;
    candidate.erase(p);
}
void exploreCave(int N){
    n = N;
    candidate.resize(n);
    iota(all(candidate), 0);
    rep(n) find(i);
    answer(s, d);
}