42272023-03-16 18:23:03Szin AttilaZárójelekcpp14Wrong answer 31/10046ms26840 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 ll maxN = 2e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 7;


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

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

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

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

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

    void update(ll v, ll pos, ll val) {
        ll vl = t[v].l, vr = t[v].r;
        ll 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<ll, ll> query(ll v, ll ql, ll qr) {
        ll 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<ll, ll> 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;

    ll n;
    cin >> n;

    vector<string> s(n);
    vector<pair<ll, pair<ll, ll> > > v(n);
    for(ll i = 0; i < n; i++) {
        cin >> s[i];
        ll 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(ll 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<ll> mo;

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

        if(ki == -1) break;

        pair<ll, ll> 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(ll 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((ll)mo.size() < n || curr != 0) cout << "-1";
    else for(ll i : mo) cout << i + 1 << ' ';
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2140 KiB
2Accepted4ms3508 KiB
subtask211/11
3Accepted3ms2484 KiB
4Accepted3ms2612 KiB
5Accepted3ms2824 KiB
6Accepted3ms3148 KiB
7Accepted3ms3740 KiB
8Accepted3ms3948 KiB
subtask36/6
9Accepted4ms5004 KiB
10Accepted4ms5092 KiB
11Accepted4ms5028 KiB
subtask414/14
12Accepted4ms5028 KiB
13Accepted4ms4692 KiB
subtask50/23
14Wrong answer4ms5028 KiB
15Wrong answer4ms4696 KiB
subtask60/19
16Wrong answer3ms4496 KiB
17Wrong answer4ms4744 KiB
18Accepted4ms5240 KiB
19Wrong answer4ms5152 KiB
20Wrong answer4ms4992 KiB
21Accepted4ms5360 KiB
22Accepted4ms5328 KiB
23Accepted4ms5328 KiB
24Accepted4ms5328 KiB
subtask70/27
25Accepted3ms4656 KiB
26Wrong answer4ms5684 KiB
27Accepted6ms6064 KiB
28Wrong answer7ms6624 KiB
29Accepted13ms9384 KiB
30Wrong answer46ms26840 KiB
31Wrong answer7ms6824 KiB
32Wrong answer8ms7336 KiB
33Wrong answer6ms6216 KiB
34Wrong answer8ms8016 KiB
35Wrong answer4ms5476 KiB
36Wrong answer9ms8420 KiB
37Accepted4ms5488 KiB
38Wrong answer4ms5368 KiB
39Wrong answer21ms13884 KiB
40Accepted4ms5412 KiB
41Accepted3ms4904 KiB
42Accepted6ms6140 KiB
43Accepted4ms5808 KiB