42252023-03-16 18:08:14Szin AttilaZárójelekcpp14Wrong answer 31/10039ms17560 KiB
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;


struct Node {
    int val, ind, l, r;
    bool leaf;
    Node() {
        val = -INF;
        ind = -INF;
        leaf = 0;
    }

    Node(int _val, int _ind, int _l, int _r) : val(_val), ind(_ind), l(_l), r(_r) {
        leaf = (l == r);
    }
};
struct SegTree {
    vector<Node> t;
    int maxn;

    void build(int v, int l, int r) {
        if(v >= 4*maxn) return;

        t[v] = {-INF, -INF, l, r};
        int mid = (l+r)/2;
        build(v*2, l, mid);
        build(v*2+1, mid+1, r);
    }

    SegTree(int n) : maxn(n) {
        t.resize(maxn*4);
        build(1, 1, maxn);
    }

    void update(int v, int pos, int val) {
        int vl = t[v].l, vr = t[v].r;
        int mid = (vl+vr)/2;

        if(t[v].leaf) {
            t[v].val = val;
            t[v].ind = pos;
            return;
        }

        if(pos <= mid) {
            update(v*2, pos, val);
        }
        else {
            update(v*2+1, pos, val);
        }

        if(t[v*2].val == t[v*2+1].val) {
            if(t[v*2].ind >= t[v*2+1].ind) {
                t[v].val = t[v*2].val;
                t[v].ind = t[v*2].ind;
            }
            else{
                t[v].val = t[v*2+1].val;
                t[v].ind = t[v*2+1].ind;
            }
        }
        else if(t[v*2].val > t[v*2+1].val) {
            t[v].val = t[v*2].val;
            t[v].ind = t[v*2].ind;
        }
        else{
            t[v].val = t[v*2+1].val;
            t[v].ind = t[v*2+1].ind;
        }
    }

    pair<int, int> query(int v, int ql, int qr) {
        int vl = t[v].l, vr = t[v].r;
        ql = max(ql, vl);
        qr = min(qr, vr);
        if(ql > qr) return {-INF, -INF};
        if(vl == ql && vr == qr) return {t[v].val, t[v].ind};

        pair<int, int> ret1 = query(v*2, ql, qr), ret2 = query(v*2+1, ql, qr);

        if(ret1.first == ret2.first) {
            if(ret1.second > ret2.second) return ret1;
            else return ret2;
        }
        if(ret1.first > ret2.first) return ret1;
        else return ret2;
    }
};

int main() {

/*#ifndef ONLINE_JUDGE
   freopen("../input.txt", "r", stdin);
   freopen("../output.txt", "w", stdout);
#endif*/
   InTheNameOfGod;

    int n;
    cin >> n;

    vector<string> s(n);
    vector<pair<int, pair<int, int> > > v(n);
    for(int i = 0; i < n; i++) {
        cin >> s[i];
        int minval = 0, curr = 0;
        for(char c : s[i]) {
            if(c == '(') curr++;
            else curr--;
            minval = min(minval, curr);
        }
        v[i] = {minval, {curr, i}};
    }

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    SegTree seg = SegTree(n+1);
    for(int i = 1; i <= n; i++) {
        seg.update(1, i, v[i-1].second.first);
        //cout << i << ": " << v[i-1].first << ", " << v[i-1].second.first << ", " << v[i-1].second.second << endl;
    }

    vector<int> mo;

    int curr = 0;
    for(int i = 0; i < n; i++) {
        int l = 0, r = n-1, ki = -1;
        while(l <= r) {
            int mid = (l+r)/2;
            if(-v[mid].first <= curr) {
                l = mid+1;
                ki = mid;
            }
            else {
                r = mid-1;
            }
        }

        if(ki == -1) break;

        pair<int, int> ret = seg.query(1, 1, ki+1);
        curr += ret.first;
        if(ret.first == -INF || curr < 0) break;

        //cout << "return: " << ret.first << ", " << ret.second << endl;
        mo.push_back(v[ret.second-1].second.second);
        seg.update(1, ret.second, -INF);
        /*cout << "\n----\n";
        for(int i = 1; i <= 7; i++) {
            cout << i << ": " << seg.t[i].ind << ", " << seg.t[i].val << ", " << seg.t[i].l << ", " << seg.t[i].r << endl;
        }
        cout << "\n----\n";*/
    }

    if((int)mo.size() < n || curr != 0) cout << "-1";
    else for(int i : mo) cout << i + 1 << ' ';
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted4ms2900 KiB
subtask211/11
3Accepted3ms2268 KiB
4Accepted3ms2484 KiB
5Accepted2ms2568 KiB
6Accepted3ms2724 KiB
7Accepted3ms3424 KiB
8Accepted3ms3492 KiB
subtask36/6
9Accepted4ms3992 KiB
10Accepted4ms4100 KiB
11Accepted4ms4368 KiB
subtask414/14
12Accepted4ms4408 KiB
13Accepted4ms4544 KiB
subtask50/23
14Wrong answer4ms4528 KiB
15Wrong answer4ms4864 KiB
subtask60/19
16Wrong answer3ms4740 KiB
17Wrong answer4ms5040 KiB
18Accepted4ms5288 KiB
19Wrong answer4ms5248 KiB
20Wrong answer4ms5248 KiB
21Accepted4ms5060 KiB
22Accepted4ms5084 KiB
23Accepted4ms5364 KiB
24Accepted4ms5624 KiB
subtask70/27
25Accepted3ms5452 KiB
26Wrong answer4ms5724 KiB
27Accepted6ms6236 KiB
28Wrong answer6ms6200 KiB
29Accepted10ms7860 KiB
30Wrong answer39ms17560 KiB
31Wrong answer7ms6116 KiB
32Wrong answer7ms6652 KiB
33Wrong answer6ms6192 KiB
34Wrong answer8ms6984 KiB
35Wrong answer4ms5564 KiB
36Wrong answer8ms7332 KiB
37Accepted4ms5716 KiB
38Wrong answer4ms5900 KiB
39Wrong answer17ms10680 KiB
40Accepted4ms5636 KiB
41Accepted3ms5328 KiB
42Accepted4ms5960 KiB
43Accepted4ms5768 KiB