問題一覧 > 通常問題

No.592 括弧の対応 (2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 216
作問者 : tailstails / テスター : butsurizukibutsurizuki
1 ProblemId : 1534 / 出題時の順位表
問題文最終更新日: 2017-02-13 00:16:36

問題文

Orino君は、以前、テキストの括弧の対応箇所を見つけるプログラムを書きました(No.22 括弧の対応)。

括弧の対応とは、

  1. 与えられた文字列から、「(」の直後に「)」が来る文字があるとき、文字列からその2つの文字を削除する。
  2. 削除された文字を新たな文字列として、1.の処理を繰り返し、文字列が空になるまで繰り返す。
そして、初めに与えられた文字列として考えたときの \(i\) 番目の文字と一緒に削除される \(j\) 番目の文字が「括弧の対応」です。
このとき、 \(j\) を、 \(i\) 番目の文字についての「括弧の対応の位置」と言うことにします。

Orino君が以前に作ったプログラムは、指定した文字についての括弧の対応の位置がわかるというものでしたが、文字を一つ一つ指定しなければならないのが不便だと思っていました。
そこで、Orino君は、テキストに含まれる全ての文字について、括弧の対応の位置が一度にわかるように、プログラムを作り直すことにしました。

「(」と「)」のみで構成される \(N\) 文字の文字列 \(S\) が与えられます。
このとき、 \(S\) に含まれる全ての文字のそれぞれについて、括弧の対応の位置を出力してください。
与えられる文字列は、全ての文字で括弧の対応があることが保証されます。

入力

\(N\)
\(S\)

1行目に、文字数を表す \(N\) が与えられます。
2行目に、文字列 \(S\) が与えられます。
\(2 \le N \le 200000\)
\(|S| = N\)

出力

\(C_1\)
\(C_2\)
\(\vdots\)
\(C_N\)

\(1\) 行目から \(N\) 行目までの \(i\) 行目に、 \(i\) 番目の文字についての括弧の対応の位置 \(C_i\) を出力してください。

サンプル

サンプル1
入力
6
()(())
出力
2
1
6
5
4
3

\(1\) 番目の文字についての括弧の対応の位置は \(2\) なので、 \(1\) 行目には 2 を出力します。
\(N=6\) なので、 \(6\) 行目まで出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。