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; }