42222023-03-16 17:42:26Szin AttilaZárójelekcpp14Wrong answer 20/10039ms17388 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) {
            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) 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
1Accepted3ms1896 KiB
2Accepted4ms2932 KiB
subtask20/11
3Accepted3ms2296 KiB
4Accepted3ms2408 KiB
5Wrong answer3ms2608 KiB
6Accepted3ms2836 KiB
7Accepted3ms3380 KiB
8Accepted3ms3380 KiB
subtask36/6
9Accepted4ms3832 KiB
10Accepted4ms3836 KiB
11Accepted4ms3984 KiB
subtask414/14
12Accepted4ms4232 KiB
13Accepted4ms4548 KiB
subtask50/23
14Wrong answer4ms4656 KiB
15Wrong answer4ms4928 KiB
subtask60/19
16Wrong answer3ms4672 KiB
17Wrong answer4ms4892 KiB
18Accepted4ms4824 KiB
19Wrong answer4ms4780 KiB
20Wrong answer4ms5040 KiB
21Accepted4ms5016 KiB
22Accepted4ms4860 KiB
23Accepted4ms4888 KiB
24Accepted4ms4924 KiB
subtask70/27
25Accepted3ms4744 KiB
26Wrong answer4ms5192 KiB
27Accepted6ms5732 KiB
28Wrong answer6ms6068 KiB
29Accepted10ms7704 KiB
30Wrong answer39ms17388 KiB
31Wrong answer6ms5932 KiB
32Wrong answer7ms6376 KiB
33Wrong answer6ms5844 KiB
34Wrong answer7ms6724 KiB
35Wrong answer4ms5308 KiB
36Wrong answer8ms6884 KiB
37Accepted4ms5516 KiB
38Wrong answer4ms5632 KiB
39Wrong answer17ms10404 KiB
40Accepted4ms5616 KiB
41Accepted3ms5344 KiB
42Accepted4ms6012 KiB
43Accepted4ms5824 KiB