40942023-03-13 22:22:51Szin AttilaZárójelekcpp14Hibás válasz 20/10039ms17620 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;
        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
1Elfogadva3ms1916 KiB
2Elfogadva4ms2960 KiB
subtask20/11
3Elfogadva3ms2332 KiB
4Elfogadva3ms2580 KiB
5Hibás válasz3ms2656 KiB
6Elfogadva3ms2884 KiB
7Elfogadva3ms3648 KiB
8Elfogadva3ms3764 KiB
subtask36/6
9Elfogadva4ms4272 KiB
10Elfogadva4ms4384 KiB
11Elfogadva4ms4508 KiB
subtask414/14
12Elfogadva4ms4600 KiB
13Elfogadva4ms4556 KiB
subtask50/23
14Hibás válasz4ms4772 KiB
15Hibás válasz4ms5008 KiB
subtask60/19
16Hibás válasz3ms4648 KiB
17Hibás válasz4ms4760 KiB
18Elfogadva4ms5124 KiB
19Hibás válasz4ms5128 KiB
20Hibás válasz4ms5128 KiB
21Elfogadva4ms5000 KiB
22Elfogadva4ms5028 KiB
23Elfogadva4ms5024 KiB
24Elfogadva4ms5024 KiB
subtask70/27
25Elfogadva3ms4980 KiB
26Hibás válasz4ms5412 KiB
27Elfogadva6ms6016 KiB
28Hibás válasz6ms6052 KiB
29Elfogadva10ms7904 KiB
30Hibás válasz39ms17620 KiB
31Hibás válasz6ms6052 KiB
32Hibás válasz7ms6596 KiB
33Hibás válasz4ms6024 KiB
34Hibás válasz7ms6820 KiB
35Hibás válasz4ms5404 KiB
36Hibás válasz8ms7064 KiB
37Elfogadva4ms5696 KiB
38Hibás válasz4ms5816 KiB
39Hibás válasz17ms10600 KiB
40Elfogadva4ms5624 KiB
41Elfogadva3ms5316 KiB
42Elfogadva4ms5956 KiB
43Elfogadva4ms5684 KiB