Submission #936999

#TimeUsernameProblemLanguageResultExecution timeMemory
936999089487Superpozicija (COCI22_superpozicija)C++14
10 / 110
76 ms15328 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("sse4,abm,avx,popcnt") #include<bits/stdc++.h> #define int long long #define quick ios::sync_with_stdio(0);cin.tie(0); #define rep(x,a,b) for(int x=a;x<=b;x++) #define repd(x,a,b) for(int x=a;x>=b;x--) #define F first #define S second #define eb emplace_back #define mp make_pair #define mt make_tuple #define all(x) x.begin(),x.end() #define sz(x) (int)(x.size()) #define lowbit(x) (x&-x) using namespace std; typedef pair<int,int> pii; void debug(){ cout<<"\n"; } template<class T,class ...U> void debug(T a,U ...b){ cout<<a<<" ",debug(b...); } const int N=2e5+7; const int INF=1e18L; pii p[N]; void solve(){ int n; cin>>n; string s; cin>>s; set<pii> st; vector<pii> v; map<pii,int> ch; int cnt=0; rep(i,0,n-1){ cin>>p[i].F>>p[i].S; --p[i].F,--p[i].S; if(s[p[i].F]!=s[p[i].S]) v.eb(p[i]); else{ if(s[p[i].F]=='(') st.insert(mp(p[i].F,1)),cnt++,ch[p[i]]=0; else { st.insert(mp(p[i].S,-1)); ch[p[i]]=1; cnt--; } } } int total=-cnt+sz(v); if(total%2){ cout<<"-1\n"; return ; } int a=total/2; int b=a-cnt; if(a<0||b<0) { cout<<"-1\n"; return ; } sort(all(v)); for(pii p2:v){ if(s[p2.F]=='('){ if(a>0){ st.insert(mp(p2.F,1)); ch[p2]=0; a--; } else{ ch[p2]=1; b--; st.insert(mp(p2.S,-1)); } } else if(s[p2.F]==')'){ if(a>0){ st.insert(mp(p2.S,1)); ch[p2]=1; a--; } else{ st.insert(mp(p2.F,-1)); ch[p2]=0; b--; } } } int sum=0; for(pii p2:st){ sum+=p2.S; if(sum<0){ cout<<"-1\n"; return ; } } rep(i,0,n-1){ cout<<ch[p[i]]<<" \n"[i==n-1]; } } signed main(){ quick int t; cin>>t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...