重複検査 / Duplicated? [第一回 アルゴリズム実技検定 過去問 D]

https://atcoder.jp/contests/past201912-open/tasks/past201912_d

解説

https://atcoder.jp/contests/past201912-open/submissions/9252399

サンプル1の説明を見ると、個数が重要そうである。
書き換えが発生していなかった場合は、全て1個であるパターンである。
書き換えが発生している場合は、ほとんど1個であるが、2個が1つと0個が1つになるはずである。
よって、個数を数えて、どっちになっているかを見ればいい。
整数xが整数yに書き換えられているとすると、整数xの個数が0個で、整数yの個数が2個になっているはずなので、
それを答える。

int N, A[201010];
int cnt[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) cnt[A[i]]++;

    int x = -1, y = -1;
    rep(i, 1, N + 1) {
        if (cnt[i] == 0) x = i;
        if (cnt[i] == 2) y = i;
    }

    if (x < 0) cout << "Correct" << endl;
    else cout << y << " " << x << endl;
}