42272023-03-16 18:23:03Szin AttilaZárójelekcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2140 KiB
2Elfogadva4ms3508 KiB
subtask211/11
3Elfogadva3ms2484 KiB
4Elfogadva3ms2612 KiB
5Elfogadva3ms2824 KiB
6Elfogadva3ms3148 KiB
7Elfogadva3ms3740 KiB
8Elfogadva3ms3948 KiB
subtask36/6
9Elfogadva4ms5004 KiB
10Elfogadva4ms5092 KiB
11Elfogadva4ms5028 KiB
subtask414/14
12Elfogadva4ms5028 KiB
13Elfogadva4ms4692 KiB
subtask50/23
14Hibás válasz4ms5028 KiB
15Hibás válasz4ms4696 KiB
subtask60/19
16Hibás válasz3ms4496 KiB
17Hibás válasz4ms4744 KiB
18Elfogadva4ms5240 KiB
19Hibás válasz4ms5152 KiB
20Hibás válasz4ms4992 KiB
21Elfogadva4ms5360 KiB
22Elfogadva4ms5328 KiB
23Elfogadva4ms5328 KiB
24Elfogadva4ms5328 KiB
subtask70/27
25Elfogadva3ms4656 KiB
26Hibás válasz4ms5684 KiB
27Elfogadva6ms6064 KiB
28Hibás válasz7ms6624 KiB
29Elfogadva13ms9384 KiB
30Hibás válasz46ms26840 KiB
31Hibás válasz7ms6824 KiB
32Hibás válasz8ms7336 KiB
33Hibás válasz6ms6216 KiB
34Hibás válasz8ms8016 KiB
35Hibás válasz4ms5476 KiB
36Hibás válasz9ms8420 KiB
37Elfogadva4ms5488 KiB
38Hibás válasz4ms5368 KiB
39Hibás válasz21ms13884 KiB
40Elfogadva4ms5412 KiB
41Elfogadva3ms4904 KiB
42Elfogadva6ms6140 KiB
43Elfogadva4ms5808 KiB