42222023-03-16 17:42:26Szin AttilaZárójelekcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1896 KiB
2Elfogadva4ms2932 KiB
subtask20/11
3Elfogadva3ms2296 KiB
4Elfogadva3ms2408 KiB
5Hibás válasz3ms2608 KiB
6Elfogadva3ms2836 KiB
7Elfogadva3ms3380 KiB
8Elfogadva3ms3380 KiB
subtask36/6
9Elfogadva4ms3832 KiB
10Elfogadva4ms3836 KiB
11Elfogadva4ms3984 KiB
subtask414/14
12Elfogadva4ms4232 KiB
13Elfogadva4ms4548 KiB
subtask50/23
14Hibás válasz4ms4656 KiB
15Hibás válasz4ms4928 KiB
subtask60/19
16Hibás válasz3ms4672 KiB
17Hibás válasz4ms4892 KiB
18Elfogadva4ms4824 KiB
19Hibás válasz4ms4780 KiB
20Hibás válasz4ms5040 KiB
21Elfogadva4ms5016 KiB
22Elfogadva4ms4860 KiB
23Elfogadva4ms4888 KiB
24Elfogadva4ms4924 KiB
subtask70/27
25Elfogadva3ms4744 KiB
26Hibás válasz4ms5192 KiB
27Elfogadva6ms5732 KiB
28Hibás válasz6ms6068 KiB
29Elfogadva10ms7704 KiB
30Hibás válasz39ms17388 KiB
31Hibás válasz6ms5932 KiB
32Hibás válasz7ms6376 KiB
33Hibás válasz6ms5844 KiB
34Hibás válasz7ms6724 KiB
35Hibás válasz4ms5308 KiB
36Hibás válasz8ms6884 KiB
37Elfogadva4ms5516 KiB
38Hibás válasz4ms5632 KiB
39Hibás válasz17ms10404 KiB
40Elfogadva4ms5616 KiB
41Elfogadva3ms5344 KiB
42Elfogadva4ms6012 KiB
43Elfogadva4ms5824 KiB