---
tags: IOI
---
# IOI2007 Day1-1 エイリアン (Aliens)

これ指数探索というという名前があったんですね

## 問題文

https://www.ioi-jp.org/ioi/2007/problem/day1/aliens-prob-j.pdf
https://oj.uz/problem/view/IOI07_aliens

2次元グリッドがあり、その一部が 5 × 5 のチェス盤の模様に赤く塗られています。
チェス盤の1マスの大きさはわかりません。
赤く塗られているマスのうち1つの座標が与えられます。
あなたは300回までグリッド上の1マスが赤く塗られているか調べられます。
チェス盤の模様の中心を答えてください。

$N ≤ 2 \times 10^9$

## 考察

$N = 2 \times 10^9$ に対して300回なので二分探索したい。
でもあるところからずっと赤というわけでもない。
こういう場合に対応できる二分探索を知っていますか？
chokudaiさんのツイートで見た気がするんですが…

- 1, 2, 4, 8, ..マス離れたところを調べる
- 途中で失敗したら、そこまでの区間に対して普通の二分探索ができる

## 実装

https://oj.uz/submission/210849

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(a) for(ll i = 0; i < a; i++)
#define all(a) begin(a), end(a)
#define sum(a) accumulate(all(a), 0LL)

ll n;
bool query(ll x, ll y){
    if(x < 1 || y < 1 || x > n || y > n) return false;
    cout << "examine " << x << ' ' << y << endl;
    string ans;
    cin >> ans;
    return ans[0] == 't';
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x, y;
    cin >> n >> x >> y;
    
    ll ng = 0, ok = 1;
    while(query(x - ok, y)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x - cen, y)) ng = cen;
        else ok = cen;
    }
    
    x -= ng;
    
    ng = 0; ok = 1;
    while(query(x, y - ok)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x, y - cen)) ng = cen;
        else ok = cen;
    }
    
    y -= ng;
    
    ng = 0; ok = 1;
    while(query(x + ok, y)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x + cen, y)) ng = cen;
        else ok = cen;
    }
    
    ll m = ok;
    x += m / 2;
    y += m / 2;
    if(query(x - m * 2, y)) x -= m * 2;
    if(query(x - m * 2, y)) x -= m * 2;
    if(query(x, y - m * 2)) y -= m * 2;
    if(query(x, y - m * 2)) y -= m * 2;
    if(query(x - m, y - m)){
        x -= m;
        y -= m;
    }
    x += m * 2;
    y += m * 2;
    cout << "solution " << x << ' ' << y << endl;
}