yukicoder - No.592

No.592　括弧の対応 (2)

括弧列？ imos でしょ

ということで 1-based に注意しながらハッシュテーブル併用してえい．

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

int imos[202020];
int cor[202020];
int mp[202020];

int main()
{
    int N;
    string S;
    
    cin >> N >> S;

    for (int i = 1; i <= N; i++) {
        if (S[i - 1] == '(') imos[i]++;
        else imos[i + 1]--;
    }
    for (int i = 1; i <= N; i++) {
        imos[i + 1] += imos[i];
    }

    for (int i = 1; i <= N; i++) {
        int v = imos[i];
        if (mp[v]) {
            int j = mp[v];
            cor[i] = j; cor[j] = i;
            mp[v] = 0;
        }
        else {
            mp[v] = i;
        }
    }

    for (int i = 1; i <= N; i++) {
        printf("%d\n", cor[i]);
        //cout << cor[i] << endl;
    }

    return 0;
}