42242023-03-16 18:05:18Szin AttilaZárójelekcpp14Wrong answer 20/10041ms17640 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;
        while(l <= r) {
            int mid = (l+r)/2;
            if(-v[mid].first <= curr) {
                l = mid+1;
                ki = mid;
            }
            else {
                r = mid-1;
            }
        }

        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
1Accepted3ms1960 KiB
2Accepted4ms3024 KiB
subtask20/11
3Accepted3ms2360 KiB
4Accepted3ms2472 KiB
5Accepted3ms2672 KiB
6Accepted3ms2896 KiB
7Accepted3ms3568 KiB
8Wrong answer3ms3784 KiB
subtask36/6
9Accepted4ms4364 KiB
10Accepted4ms4568 KiB
11Accepted4ms4788 KiB
subtask414/14
12Accepted4ms4876 KiB
13Accepted4ms4984 KiB
subtask50/23
14Wrong answer4ms5232 KiB
15Wrong answer4ms5160 KiB
subtask60/19
16Wrong answer3ms4776 KiB
17Wrong answer4ms4980 KiB
18Accepted4ms5104 KiB
19Wrong answer4ms5192 KiB
20Wrong answer4ms5492 KiB
21Accepted4ms5308 KiB
22Accepted4ms5280 KiB
23Accepted4ms5284 KiB
24Accepted4ms5412 KiB
subtask70/27
25Accepted3ms5184 KiB
26Wrong answer4ms5504 KiB
27Accepted6ms6020 KiB
28Wrong answer6ms5988 KiB
29Accepted10ms7940 KiB
30Wrong answer41ms17640 KiB
31Wrong answer6ms6120 KiB
32Wrong answer7ms6816 KiB
33Wrong answer6ms6124 KiB
34Wrong answer8ms6916 KiB
35Wrong answer4ms5488 KiB
36Wrong answer8ms7160 KiB
37Accepted4ms5448 KiB
38Wrong answer4ms5960 KiB
39Wrong answer17ms10688 KiB
40Accepted4ms5896 KiB
41Accepted3ms5548 KiB
42Accepted4ms6184 KiB
43Accepted4ms5984 KiB