問題概要

対応のとれているカッコ列 $S$ が与えられる。対応する左かっこ '(' と右かっこ ')' が、それぞれ $S$ の何番目と何番目であるかを順に求めよ。

制約

$1 \le |S| \le 2 \times 10^{5}$

メモ

詳しい解説はここにあるのでメモ程度に。

github.com

スタックには左カッコ '(' に対応する index を格納していく。')' に対応する '(' の index は、スタックの末尾にある要素を見ていけば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    vector<int> stk;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '(') stk.push_back(i);
        else {
            cout << stk.back()+1 << " " << i+1 << endl;
            stk.pop_back();
        }
    }
}