Codeforces Round #371 (Div. 2) D. Searching Rectangles

問題

codeforces.com

考察

大きな範囲をカバーするクエリから徐々に片側を縮めてゆくことで、1辺の境界が分かります。
また、四角形は2つあるので、クエリの答えが「2->1」または「2->0」になった箇所で1つ、「1->0」「2->0」になった箇所にもう1つの辺があることがわかります。

辺は大きいですが、端から端まで順番に見ると0->...->1->...->2になるので、二分探索が使えます。
 2^{16}が最大なので、16回程度で求めることができます。
4辺 * 2つ = 8回繰り返し、16 * 8 = 128回程度で列挙が完了します。

さて、求めた辺ですが、このままだとどちらがどちらの四角形なのかがわかりません。
そこで有効な全てのパターンでクエリを投げ、それぞれに対して1が返ってくるかどうかで正しい組み合わせを判定します。
これはそれぞれの辺に2つの候補があるので、 2^{4} = 16回で判定できます。

よって、最大でも150回程度で全ての処理が終わり、制限内にACが取れます。

実装上の工夫

やることは単純ですが、実装がかなり厄介でした。
二分探索部分を共通の関数にしたり、うまいこと配列に押しこんだりしてみました。

コード

int n;

int bin(vi pos, int move_i, int target, bool up) {
    int lb = 0;
    int ub = n + 1;
    while (ub - lb > 1) {
        int med = (ub + lb) / 2;
        if (up)
            pos[move_i] = med;
        else
            pos[move_i] = n + 1 - med;

        cout << "?";
        rep(i, 4)cout << " " << pos[i];
        cout << endl;
        fflush(stdout);

        int res;
        cin >> res;

        if (res < target)
            lb = med;
        else
            ub = med;
    }

    if(up)
        return ub;
    else
        return n + 1 - ub;
}

vi make(int S, vector<pii>& pos) {
    vi tmp(4,0);
    rep(j, 4) {
        if( ((S>>j) & 1) == 0 )
            tmp[j] = pos[j].first;
        else
            tmp[j] = pos[j].second;
    }
    return tmp;
}

bool check(vi& tmp, vector<pii>& pos) {
    cout << "?";
    rep(j, 4)
        cout << " " << tmp[j];
    cout << endl;
    fflush(stdout);

    int t;
    cin >> t;
    return (t == 1);
}

int main() {
    cin >> n;
    vector<pii> pos(4);

    // bottom
    pos[0].first = bin({0, 1, n, n}, 0, 1, false);
    pos[0].second = bin({0, 1, n, n}, 0, 2, false);

    // left
    pos[1].first = bin({1, 0, n, n}, 1, 1, false);
    pos[1].second = bin({1, 0, n, n}, 1, 2, false);

    // top
    pos[2].first = bin({1, 1, 0, n}, 2, 1, true);
    pos[2].second = bin({1, 1, 0, n}, 2, 2, true);

    // right
    pos[3].first = bin({1, 1, n, 0}, 3, 1, true);
    pos[3].second = bin({1, 1, n, 0}, 3, 2, true);

    rep(S, 1<<4) {
        int S2 = S ^ ((1<<5) - 1);

        vi t1 = make(S, pos);
        vi t2 = make(S2, pos);

        if(t1[0] <= t1[2] && t1[1] <= t1[3] && t2[0] <= t2[2] && t2[1] <= t2[3]) {
            bool ok = check(t1, pos) && check(t2, pos);
            if(ok) {
                cout << "!";
                rep(i, 4)
                    cout << " " << t1[i];
                rep(i, 4)
                    cout << " " << t2[i];
                cout << endl;
                fflush(stdout);
                return 0;
            }
        }
    }

    return 0;
}