Submission #672131

#	Time	Username	Problem	Language	Result	Execution time	Memory
672131		Victor	Superpozicija (COCI22_superpozicija)	C++17	110 / 110	117 ms	42440 KiB

Main

// #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],pos=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);
        tie(val,pos)=min(ii(l->val,l->pos),ii(r->val,r->pos));
    }

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

int A[100005],B[100005];
int arr[200005];

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,arr[i]=INF;
        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<<'\n';
            continue;
        }

        trav(pair,pairs) {
            int a,b;
            tie(a,b)=pair;
            ++open;
            arr[a]=-b;
            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);
        Node query_tree(0,2*n,arr);
        rep(_,0,open-n/2) {
            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)=query_tree.query(lo,2*n);
            //cout<<"a = "<<a<<" b = "<<b<<endl;
            if(a>=INF) {
                walk_tree.val=-1;
                break;
            }
            a=-a;
            query_tree.add(b,b+1,INF);

            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<<'\n';
            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<<'\n';
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 70 / 70