53512023-04-26 10:48:03ZsofiaKeresztelyZárójelekcpp14Accepted 100/10037ms7488 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    vector<pii> reql, reqr;
    vector<int> dif(n+1), op(n+1, 0), opp(n);
    for (int i=1; i<=n; i++){
        string s;
        cin >> s;
        int left = 0, right = 0, need = 0;
        for (char c : s){
            if (c == '(') left++;
            else right++;
            if (left + need < right) need++;
        }
        dif[i] = left - right;
        if (left > right){
            reql.push_back({need, i});
        }
        else{
            left = 0; right = 0; need = 0;
            for (int i=s.size()-1; i>=0; i--){
                if (s[i] == '(') left++;
                else right++;
                if (right + need < left) need++;
            }
            reqr.push_back({need, i});
        }
    }
    reql.push_back({0, 0});
    reqr.push_back({0, 0});
    sort(reql.begin(), reql.end());
    sort(reqr.begin(), reqr.end());
    priority_queue<pii> pq;
    int ind = 0, provl = 0, cnt = 1, provr = 0;
    while (ind + 1 < reql.size() && !reql[ind+1].fi){
        ind++;
        pq.push({dif[reql[ind].se], reql[ind].se});
    }
    while (!pq.empty()){
        pii p = pq.top();
        pq.pop();
        provl += p.fi;
        op[p.se] = cnt;
        cnt++;
        while (ind + 1 < reql.size() && reql[ind+1].fi <= provl){
            ind++;
            pq.push({dif[reql[ind].se], reql[ind].se});
        }
        while (ind > 0 && reql[ind].fi > provl){
            if (!op[reql[ind].se]){
                cout << -1;
                return 0;
            }
            ind--;
        }
    }
    ind = 0;
    cnt = n;
    while (ind + 1 < reqr.size() && !reqr[ind+1].fi){
        ind++;
        pq.push({-1*dif[reqr[ind].se], reqr[ind].se});
    }
    while (!pq.empty()){
        pii p = pq.top();
        pq.pop();
        provr += p.fi;
        op[p.se] = cnt;
        cnt--;
        while (ind + 1 < reqr.size() && reqr[ind+1].fi <= provr){
            ind++;
            pq.push({-1*dif[reqr[ind].se], reqr[ind].se});
        }
        while (ind > 0 && reqr[ind].fi > provr){
            if (!op[reqr[ind].se]){
                cout << -1;
                return 0;
            }
            ind--;
        }
    }
    if (provl != provr){
        cout << -1;
        return 0;
    }
    for (int i=1; i<=n; i++){
        if (!op[i]){
            cout << -1;
            return 0;
        }
        opp[op[i]-1] = i;
    }
    for (int x : opp){
        cout << x << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Accepted9ms2220 KiB
subtask211/11
3Accepted3ms2200 KiB
4Accepted3ms2420 KiB
5Accepted3ms2504 KiB
6Accepted3ms2616 KiB
7Accepted8ms3200 KiB
8Accepted8ms3496 KiB
subtask36/6
9Accepted8ms3520 KiB
10Accepted8ms3720 KiB
11Accepted8ms3852 KiB
subtask414/14
12Accepted8ms3816 KiB
13Accepted8ms3804 KiB
subtask523/23
14Accepted8ms4080 KiB
15Accepted8ms4272 KiB
subtask619/19
16Accepted8ms4204 KiB
17Accepted9ms4308 KiB
18Accepted9ms4332 KiB
19Accepted8ms4516 KiB
20Accepted8ms4440 KiB
21Accepted7ms4488 KiB
22Accepted7ms4496 KiB
23Accepted7ms4492 KiB
24Accepted7ms4496 KiB
subtask727/27
25Accepted8ms4540 KiB
26Accepted10ms4816 KiB
27Accepted10ms4764 KiB
28Accepted12ms5084 KiB
29Accepted14ms5476 KiB
30Accepted37ms7488 KiB
31Accepted9ms5148 KiB
32Accepted10ms5180 KiB
33Accepted9ms4980 KiB
34Accepted12ms5192 KiB
35Accepted8ms4916 KiB
36Accepted12ms5292 KiB
37Accepted8ms4944 KiB
38Accepted8ms5012 KiB
39Accepted19ms6064 KiB
40Accepted6ms4972 KiB
41Accepted4ms4936 KiB
42Accepted8ms5276 KiB
43Accepted7ms5104 KiB