Vacant Seat [AtCoder Petrozavodsk Contest 001 C]

https://beta.atcoder.jp/contests/apc001/tasks/apc001_c

前提知識

• 二分探索

解説

https://beta.atcoder.jp/contests/apc001/submissions/2064651

色々な制約がある。

• 同性どうしが隣り合う席に座らない
• Nは奇数
• 1つだけ空席がある

ここから以下のような性質を導く。
「[0,i)で空席が無ければ、iが偶数なら席0と席iの性別は同じで、iが奇数なら席0と席iの性別は異なる」
これを使って二分探索していこう。
　
席0を基準に考えるので、席0を聞いてa0としておこう。
（席0が空席なら終了）
　
f(l, r) := 席[l,r)を探索する
まず中心を聞く md = (l / r) / 2
中心が空席ならその時点で終了。
中心が上の性質を満たすならば[l,md]に空席は無いので、[md+1,r)を探索する。
満たさないなら[l,md)に空席が存在するので、[l,md)を探索する。
探索範囲は半分半分になっていくので二分探索的に探せるので20回以内に特定できる。

int N;
#define vacant "Vacant"
#define male "Male"
#define female "Female"
//---------------------------------------------------------------------------------------------------
string a0;
string ask(int i) {
    printf("%d\n", i);
    fflush(stdout);
    string res; cin >> res;
    return res;
}
//---------------------------------------------------------------------------------------------------
void f(int l, int r) {
    int md = (l + r) / 2;
 
    auto res = ask(md);
    if (res == vacant) return;
 
    if ((md % 2 == 0 and a0 == res) or (md % 2 == 1 and a0 != res)) f(md + 1, r);
    else f(l, md);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
 
    a0 = ask(0);
    if (a0 == vacant) return;
 
    f(1, N);
}