APC001 C - Vacant Seat

問題ページ
C - Vacant Seat

考えたこと

• 頂点数が奇数で円環状になっているグラフが2部グラフなわけはないので空席があるのはそれはそう
• クエリ回数が20回なのでlogオーダーの計算量しかありえなさそう
• 空席が絶対にある範囲をもって二分探索っぽいことをすればいい気持ちになる
• 2つの席の間の席が奇数か偶数か、その二つの席に座ってるのが同性か異性かで2つの席の間に空席が絶対に存在するかどうか判定できる
• logNならクエリ回数は20回あれば足りる

インタラクティブ系の簡単な問題、大体にぶたんな気がしてきた
queryを投げる関数を作っておいて#ifdefで手元でテストするときは自動で終わるようにしておくとデバッグが楽

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define PB push_back

const ll LLINF = (1LL << 60);
const int INF = (1LL << 30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> T ceil(T a, T b) { return a / b + !!(a%b); }
template<class S, class T>
ostream &operator <<(ostream& out, const pair<S, T>& a) {
    out << '(' << a.first << ',' << a.second << ')';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const vector<T>& a) {
    out << '[';
    REP(i, a.size()) { out << a[i]; if (i != a.size() - 1)out << ','; }
    out << ']';
    return out;
}

int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };

signed main(void) {
    int n;
    cin >> n;

    // #define DEBUG
    VI ans = { 1, 2, 1, 2, 1, 0, 2, 1, 2 };
    auto query = [&](int mid) -> int {
       #ifdef DEBUG
                cout << mid << "," << ans[mid] << endl;
                if (ans[mid] == 0) exit(0);
                return ans[mid];
       #else
                cout << mid << endl;
                string res;
                cin >> res;
                if (res == "Vacant") {
                    cerr << "end" << endl;
                    exit(0);
                }
                else if (res == "Male") return 1;
                else if (res == "Female") return 2;
                else exit(-1);
       #endif
    };

    VI d(n);
    // [lb, ub)
    int lb = 1, ub = n;
    auto check = [&](int mid) -> bool {
        d[mid] = query(mid);
        int len1 = mid - lb, len2 = ub - mid - 1;
        if (len1 % 2) {
            if (d[lb-1] == d[mid]) return true;
            return false;
        }
        else {
            if (d[lb-1] == d[mid]) return false;
            return true;
        }
    };

    // 席0についてクエリ
    d[0] = query(0);

    while (ub - lb > 1) {
        int mid = (ub + lb) / 2;
        // cout << lb << "," << mid << "," << ub << endl;
        if (check(mid)) {
            lb = mid + 1;
        }
        else {
            ub = mid;
        }
    }

    query(lb);

    return 0;
}