53512023-04-26 10:48:03ZsofiaKeresztelyZárójelekcpp14Elfogadva 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 << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Elfogadva9ms2220 KiB
subtask211/11
3Elfogadva3ms2200 KiB
4Elfogadva3ms2420 KiB
5Elfogadva3ms2504 KiB
6Elfogadva3ms2616 KiB
7Elfogadva8ms3200 KiB
8Elfogadva8ms3496 KiB
subtask36/6
9Elfogadva8ms3520 KiB
10Elfogadva8ms3720 KiB
11Elfogadva8ms3852 KiB
subtask414/14
12Elfogadva8ms3816 KiB
13Elfogadva8ms3804 KiB
subtask523/23
14Elfogadva8ms4080 KiB
15Elfogadva8ms4272 KiB
subtask619/19
16Elfogadva8ms4204 KiB
17Elfogadva9ms4308 KiB
18Elfogadva9ms4332 KiB
19Elfogadva8ms4516 KiB
20Elfogadva8ms4440 KiB
21Elfogadva7ms4488 KiB
22Elfogadva7ms4496 KiB
23Elfogadva7ms4492 KiB
24Elfogadva7ms4496 KiB
subtask727/27
25Elfogadva8ms4540 KiB
26Elfogadva10ms4816 KiB
27Elfogadva10ms4764 KiB
28Elfogadva12ms5084 KiB
29Elfogadva14ms5476 KiB
30Elfogadva37ms7488 KiB
31Elfogadva9ms5148 KiB
32Elfogadva10ms5180 KiB
33Elfogadva9ms4980 KiB
34Elfogadva12ms5192 KiB
35Elfogadva8ms4916 KiB
36Elfogadva12ms5292 KiB
37Elfogadva8ms4944 KiB
38Elfogadva8ms5012 KiB
39Elfogadva19ms6064 KiB
40Elfogadva6ms4972 KiB
41Elfogadva4ms4936 KiB
42Elfogadva8ms5276 KiB
43Elfogadva7ms5104 KiB