Codeforces Round 1125 (Div. 3) B - Did Not Go to Print
- サイト
- Codeforces
- コンテスト
- Codeforces Round 1125 (Div. 3)
- 問題
- B - Did Not Go to Print
文書 と、最初は空のプリンターのメモリがあります。 番目の操作 は次のいずれかです。
1:文書 をメモリの一番上に積む2:メモリが空でなければ、一番上の文書を印刷してメモリから取り除く。空なら文書 を印刷する3:文書 を印刷する
すべての操作のあとで、一度も印刷されなかった文書の番号を昇順に出力してください( の総和 )。
メモリは「最後に積んだものから取り出す」ので、スタックそのものです。操作を順にシミュレーションして、印刷された文書を記録すれば、残りが答えです。
1:スタックに を push する2:スタックが空でなければ pop した文書を、空なら を印刷済みにする3: を印刷済みにする
なお、2 でスタックが空でないときは、文書 自身は印刷されません。2 の操作では文書 はメモリにも入らないので、その文書が印刷されることはもうありません。
各操作は なので、全体で です。
Python
for _ in range(int(input())): N = int(input()) S = input() t = [] l = [] for i, c in enumerate(S): if c == "1": l.append(i) elif c == "2": if l: t.append(l.pop()) else: t.append(i) else: t.append(i) ans = set(range(N)) - set(t) print(len(ans)) print(*[i + 1 for i in sorted(ans)])l がメモリのスタック、t が印刷された文書のリストです。文書番号は 0 始まりで持っておき、出力するときに 1 を足しています。 のときは print(*[]) が空行を出力するので、そのままで大丈夫です。