コンテンツにスキップ

Codeforces Round 1125 (Div. 3) B - Did Not Go to Print

サイト
Codeforces
コンテスト
Codeforces Round 1125 (Div. 3)
問題
B - Did Not Go to Print

文書 1,…,n1, \dots, n と、最初は空のプリンターのメモリがあります。ii 番目の操作 sis_i は次のいずれかです。

  • 1:文書 ii をメモリの一番上に積む
  • 2:メモリが空でなければ、一番上の文書を印刷してメモリから取り除く。空なら文書 ii を印刷する
  • 3:文書 ii を印刷する

すべての操作のあとで、一度も印刷されなかった文書の番号を昇順に出力してください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

メモリは「最後に積んだものから取り出す」ので、スタックそのものです。操作を順にシミュレーションして、印刷された文書を記録すれば、残りが答えです。

  • 1:スタックに ii を push する
  • 2:スタックが空でなければ pop した文書を、空なら ii を印刷済みにする
  • 3:ii を印刷済みにする

なお、2 でスタックが空でないときは、文書 ii 自身は印刷されません。2 の操作では文書 ii はメモリにも入らないので、その文書が印刷されることはもうありません。

各操作は O(1)O(1) なので、全体で O(n)O(n) です。

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 を足しています。k=0k = 0 のときは print(*[]) が空行を出力するので、そのままで大丈夫です。