oj.uz

Submission #672128

# Submission time Handle Problem Language Result Execution time Memory
672128 2022-12-14T19:46:04 Z Victor Superpozicija (COCI22_superpozicija) C++17
20 / 110
 1000 ms 20432 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n,prefix[200005];
string s;
vii pairs;
umap<int,int> active;

struct Node {
    Node *l,*r;
    int lo,hi,val,pos,madd=0;

    Node(int L,int R,int arr[]) : lo(L),hi(R) {
        if(hi-lo==1) val=arr[lo];
        else {
            int mid=(lo+hi)/2;
            l=new Node(lo,mid,arr);
            r=new Node(mid,hi,arr);
            tie(val,pos)=min(ii(l->val,l->pos),ii(r->val,r->pos));
        }
    }

    ii query(int L,int R) {
        if(hi<=L||R<=lo) return {INF,INF};
        if(L<=lo&&hi<=R) return {val,pos};
        push();
        return min(l->query(L,R),r->query(L,R));
    }

    int walk() {
        if(hi-lo==1) return lo+(val==0);
        push();
        if(r->val==0) return r->walk();
        return l->walk();
    }

    void add(int L,int R,int x) {
        if(hi<=L||R<=lo) return;
        if(L<=lo&&hi<=R) {
            madd+=x;
            val+=x;
            return;
        }

        push();
        l->add(L,R,x);
        r->add(L,R,x);
        val=min(l->val,r->val);
    }

    void push() {
        if(madd) {
            l->add(lo,hi,madd);
            r->add(lo,hi,madd);
            madd=0;
        }
    }
};

int A[100005],B[100005];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int tc;
    cin>>tc;
    while(tc--) {
        cin>>n>>s;
        rep(i,0,2*n) prefix[i]=0;
        pairs.clear();
        active.clear();

        int open=0,closed=0;
        rep(i,0,n) {
            int a,b;
            cin>>a>>b;
            --a; --b;
            A[i]=a;
            B[i]=b;

            if(s[a]==s[b]) {
                if(s[a]=='(') prefix[a]=1,++open;
                else prefix[b]=-1,++closed;
            }
            else pairs.emplace_back(a,b);
        }

        if(open>n/2||closed>n/2||n%2) {
            cout<<-1<<endl;
            continue;
        }

        trav(pair,pairs) {
            int a,b;
            tie(a,b)=pair;
            ++open;
            if(s[a]=='(') prefix[a]=1;
            else prefix[b]=1;
        }

        rep(i,0,2*n) {
            if(prefix[i]) active[i]=prefix[i];
            if(i) prefix[i]+=prefix[i-1];
        }

        Node walk_tree(0,2*n,prefix);
        rep(_,0,open-n/2) {
            int best=-1;
            int lo=walk_tree.walk();
            rep(i,0,sz(pairs)) if(pairs[i].first>=lo) {
                if(best==-1) best=i;
                else if(pairs[i].second>pairs[best].second) best=i;
            }
            if(best==-1) {
                walk_tree.val=-1;
                break;
            }

            int a,b;
            tie(a,b)=pairs[best];
            pairs.erase(pairs.begin()+best);

            if(active.count(a)) {
                active.erase(a);
                active[b]=-1;

            } else {
                active.erase(b);
                active[a]=-1;
            }

            walk_tree.add(a,2*n,-1);
            walk_tree.add(b,2*n,-1);
            if(walk_tree.val<0) break;
        }

        if(walk_tree.val<0) {
            cout<<-1<<endl;
            continue;
        }
        assert(sz(active)==n);
        //trav(item,active) cout<<"pos = "<<item.first<<" type = "<<item.second<<endl;
        rep(i,0,n) cout<<active.count(B[i])<<' ';
        cout<<endl;
    }
    _Exit(0);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 17740 KB Output is correct
2 Correct 26 ms 1104 KB Output is correct
3 Correct 59 ms 18252 KB Output is correct
4 Correct 57 ms 18312 KB Output is correct
5 Correct 57 ms 18252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2568 KB Output is correct
2 Correct 17 ms 1680 KB Output is correct
3 Correct 13 ms 1728 KB Output is correct
4 Correct 17 ms 2004 KB Output is correct
5 Correct 13 ms 2132 KB Output is correct
6 Correct 8 ms 2008 KB Output is correct
7 Correct 10 ms 2280 KB Output is correct
8 Correct 14 ms 2616 KB Output is correct
9 Correct 14 ms 2912 KB Output is correct
10 Correct 16 ms 3300 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 46 ms 19952 KB Output is correct
3 Correct 214 ms 19252 KB Output is correct
4 Correct 371 ms 17740 KB Output is correct
5 Correct 530 ms 20432 KB Output is correct
6 Correct 919 ms 19052 KB Output is correct
7 Correct 21 ms 13728 KB Output is correct
8 Execution timed out 1027 ms 16324 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 17740 KB Output is correct
2 Correct 26 ms 1104 KB Output is correct
3 Correct 59 ms 18252 KB Output is correct
4 Correct 57 ms 18312 KB Output is correct
5 Correct 57 ms 18252 KB Output is correct
6 Correct 16 ms 2568 KB Output is correct
7 Correct 17 ms 1680 KB Output is correct
8 Correct 13 ms 1728 KB Output is correct
9 Correct 17 ms 2004 KB Output is correct
10 Correct 13 ms 2132 KB Output is correct
11 Correct 8 ms 2008 KB Output is correct
12 Correct 10 ms 2280 KB Output is correct
13 Correct 14 ms 2616 KB Output is correct
14 Correct 14 ms 2912 KB Output is correct
15 Correct 16 ms 3300 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 46 ms 19952 KB Output is correct
18 Correct 214 ms 19252 KB Output is correct
19 Correct 371 ms 17740 KB Output is correct
20 Correct 530 ms 20432 KB Output is correct
21 Correct 919 ms 19052 KB Output is correct
22 Correct 21 ms 13728 KB Output is correct
23 Execution timed out 1027 ms 16324 KB Time limit exceeded
24 Halted 0 ms 0 KB -