// #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';
}
_Exit(0);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
33740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
3156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
33740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
