問題概要（インタラクティブ）

最初に、正の整数 $N$ が与えられて、ゲームをする。あなたは高橋君で先手である。相手は青木君で後手である。

交互に、1 以上 $2N+1$ 以下の整数を言っていく。ただし、すでに誰かが言った整数は言えない。先に整数を言えなくなった方が負けである。このゲームに勝ってください。

制約

$1 \le N \le 1000$

考えたこと

やりたいことはシンプルで、「まだ言われていない整数値」をなんでもいいから言っていけばよい。まだ言われていない整数値を求めるためには、次のデータを管理しておこう。

already[v]：整数 $v$ がすでに言われていたら True / 言われていなかったら False

これをサイズ $2N+2$ の配列として宣言して、False で初期化しておく。そして、新たに整数 $x$ が言われたら（もしくは言ったら）、already[x] を True にしていけばよい。

最後に、「まだ言われていない整数」をどのように探すかを考える。たとえば、まだ言われていない最小の整数を言っていくことが考えられる。下のコード例のように、まだ言われていない最小の整数を探索して、言っていけばよい。

計算量

「まだ言われていない整数」を探すのに $O(N)$ の計算量を要するので、全体の計算量は $O(N^{2})$ となる。

（なお、しゃくとり法を取り入れて工夫すると、全体の計算量を $O(N)$ にすることもできる）

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, aoki;
    cin >> N;

    // すでに言っていない最小の数を返す関数
    vector<int> already(N*2 + 2, false);
    auto min_not_already = [&]() -> int {
        int res = 1;
        while (already[res]) res++;
        return res;
    };

    for (int i = 0; i < N+1; i++) {
        // 高橋君が数を宣言する
        int val = min_not_already();
        cout << val << endl;
        already[val] = true;

        // 青木君が数を宣言する
        cin >> aoki;
        already[aoki] = true;
        if (aoki == 0) break;
    }
}