はまやんはまやんはまやん

hamayanhamayan's blog

ねこのあな [パソコン甲子園2019 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0408

前提知識

  • スタック

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0408/judge/3897197/C++14

問題文で定義されている横穴は、プログラミングの世界でスタックと呼ばれる構造である。
スタックとは、最初に入れた要素が最後に出てきて、最後に入れた要素が最初に出てくるデータ構造。
このデータ構造を使ってシミュレーションしてみて、不整合が無いかチェックする。
起こりうる不整合は以下の通りである。

  • 横穴に猫がいないのに、出ていった猫がいる
  • 横穴から出ていった猫と、記録にある出ていった猫が違う
  • もうすでに横穴にその猫がいるのに、横穴にその猫が入ろうとしている(入力例2)

猫が入っているかどうかは、フラグでも作っておこう。
flag[i] := 猫iが横穴に入っているならtrue

int L, C[1010];
int flag[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L;

    stack<int> stk;
    rep(i, 0, L) {
        int c; cin >> c;
        if (0 < c) {
            // 入る
            if (flag[c]) {
                cout << i + 1 << endl;
                return;
            }

            flag[c] = true;
            stk.push(c);
        } else {
            // 出る
            c *= -1;
            if (!flag[c] or stk.top() != c)
            {
                cout << i + 1 << endl;
                return;
            }
            stk.pop();
            flag[c] = false;
        }
    }
    cout << "OK" << endl;
}