# ARC179-C Beware of Overflow

1771diff
https://atcoder.jp/contests/arc179/tasks/arc179_c

## 解法

現在黒板に書かれている値の中で最小値と最大値を選んで消して足すという操作を$N - 1$回行えば良い。

よって黒板に書かれている値を常に値の昇順に管理できれば良い。$N \le 1000$なので値を消す操作は愚直にやって良い。値を挿入する操作に関しては愚直に行うとクエリ回数を超過するだろう。そこで二分探索でinsert操作を高速化すれば良い。
- insert一回につきおおよそ$\log_{2}N$回のクエリを投げる必要がある。$\log_{2}1000$が大体10くらい。

insert操作を大体$2N$回行うため、質問回数は$20000$回くらいだろう。実際はクエリの質問回数の定数倍も小さいからもっと余裕あると思う。

## 実装

#include <bits/stdc++.h>

int table[2500][2500];

int ask(int i, int j) {
    if (table[i][j] != -1) return table[i][j];
    std::cout << '?' << ' ' << i << ' ' << j << std::endl;
    int Q;
    std::cin >> Q;
    if (Q == -1) std::exit(0);
    return table[i][j] = Q;
}

std::vector<int> cur;

void insert(int i) {
    if (cur.empty()) {
        cur.push_back(i);
        return;
    }
    if (ask(i, cur[0])) {
        cur.insert(cur.begin(), i);
        return;
    }
    else if (!ask(i, cur.back())) {
        cur.push_back(i);
        return;
    }
    int ok{0}, ng{(int)cur.size()};
    while (ng - ok > 1) {
        int mid{(ok + ng) / 2};
        if (!ask(i, cur[mid])) {
            ok = mid;
        }
        else {
            ng = mid;
        }
    }
    cur.insert(cur.begin() + ng, i);
}

int main() {

    for (int i{} ; i < 2500 ; i++) for (int j{} ; j < 2500 ; j++) 
        table[i][j] = -1;

    int N;
    std::cin >> N;
    for (int i{1} ; i <= N ; i++) insert(i);
    for (int i{} ; i < N - 1 ; i++) {
        int p{cur[0]}, q{cur[cur.size() - 1]};
        std::cout << '+' << ' ' << p << ' ' << q << std::endl;
        cur.erase(cur.begin());
        cur.pop_back();
        int v;
        std::cin >> v;
        if (v == -1) std::exit(0);
        insert(v);
    }
    std::cout << '!' << std::endl;
}

[提出リンク](https://atcoder.jp/contests/arc179/submissions/58089544)

## 感想

実装もっとごみごみするかなと思ったが、意外とすっきり書けた。