5351 2023. 04. 26 10:48:03 ZsofiaKeresztely Zárójelek cpp14 Elfogadva 100/100 37ms 7488 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Elfogadva 9ms 2220 KiB
subtask2 11/11
3 Elfogadva 3ms 2200 KiB
4 Elfogadva 3ms 2420 KiB
5 Elfogadva 3ms 2504 KiB
6 Elfogadva 3ms 2616 KiB
7 Elfogadva 8ms 3200 KiB
8 Elfogadva 8ms 3496 KiB
subtask3 6/6
9 Elfogadva 8ms 3520 KiB
10 Elfogadva 8ms 3720 KiB
11 Elfogadva 8ms 3852 KiB
subtask4 14/14
12 Elfogadva 8ms 3816 KiB
13 Elfogadva 8ms 3804 KiB
subtask5 23/23
14 Elfogadva 8ms 4080 KiB
15 Elfogadva 8ms 4272 KiB
subtask6 19/19
16 Elfogadva 8ms 4204 KiB
17 Elfogadva 9ms 4308 KiB
18 Elfogadva 9ms 4332 KiB
19 Elfogadva 8ms 4516 KiB
20 Elfogadva 8ms 4440 KiB
21 Elfogadva 7ms 4488 KiB
22 Elfogadva 7ms 4496 KiB
23 Elfogadva 7ms 4492 KiB
24 Elfogadva 7ms 4496 KiB
subtask7 27/27
25 Elfogadva 8ms 4540 KiB
26 Elfogadva 10ms 4816 KiB
27 Elfogadva 10ms 4764 KiB
28 Elfogadva 12ms 5084 KiB
29 Elfogadva 14ms 5476 KiB
30 Elfogadva 37ms 7488 KiB
31 Elfogadva 9ms 5148 KiB
32 Elfogadva 10ms 5180 KiB
33 Elfogadva 9ms 4980 KiB
34 Elfogadva 12ms 5192 KiB
35 Elfogadva 8ms 4916 KiB
36 Elfogadva 12ms 5292 KiB
37 Elfogadva 8ms 4944 KiB
38 Elfogadva 8ms 5012 KiB
39 Elfogadva 19ms 6064 KiB
40 Elfogadva 6ms 4972 KiB
41 Elfogadva 4ms 4936 KiB
42 Elfogadva 8ms 5276 KiB
43 Elfogadva 7ms 5104 KiB