42242023-03-16 18:05:18Szin AttilaZárójelekcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1960 KiB
2Elfogadva4ms3024 KiB
subtask20/11
3Elfogadva3ms2360 KiB
4Elfogadva3ms2472 KiB
5Elfogadva3ms2672 KiB
6Elfogadva3ms2896 KiB
7Elfogadva3ms3568 KiB
8Hibás válasz3ms3784 KiB
subtask36/6
9Elfogadva4ms4364 KiB
10Elfogadva4ms4568 KiB
11Elfogadva4ms4788 KiB
subtask414/14
12Elfogadva4ms4876 KiB
13Elfogadva4ms4984 KiB
subtask50/23
14Hibás válasz4ms5232 KiB
15Hibás válasz4ms5160 KiB
subtask60/19
16Hibás válasz3ms4776 KiB
17Hibás válasz4ms4980 KiB
18Elfogadva4ms5104 KiB
19Hibás válasz4ms5192 KiB
20Hibás válasz4ms5492 KiB
21Elfogadva4ms5308 KiB
22Elfogadva4ms5280 KiB
23Elfogadva4ms5284 KiB
24Elfogadva4ms5412 KiB
subtask70/27
25Elfogadva3ms5184 KiB
26Hibás válasz4ms5504 KiB
27Elfogadva6ms6020 KiB
28Hibás válasz6ms5988 KiB
29Elfogadva10ms7940 KiB
30Hibás válasz41ms17640 KiB
31Hibás válasz6ms6120 KiB
32Hibás válasz7ms6816 KiB
33Hibás válasz6ms6124 KiB
34Hibás válasz8ms6916 KiB
35Hibás válasz4ms5488 KiB
36Hibás válasz8ms7160 KiB
37Elfogadva4ms5448 KiB
38Hibás válasz4ms5960 KiB
39Hibás válasz17ms10688 KiB
40Elfogadva4ms5896 KiB
41Elfogadva3ms5548 KiB
42Elfogadva4ms6184 KiB
43Elfogadva4ms5984 KiB