#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
void solve(){
int n;
cin>>n;
if(n&1){
cout<<-1<<'\n';
return;
}
string str;
cin>>str;
vector<pair<int,int>> pairs;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
a--;
b--;
pairs.push_back({a,b});
}
bool tf2=true;
for(auto v:pairs){
if((v.f+1)!=v.s) tf2=false;
}
if(n<=10){
for(int i=0;i<(1<<n);i++){
vector<pair<int,int>> cur;
vector<int> ans;
for(int j=0;j<n;j++){
auto v=pairs[j];
if(i&(1<<j)){
ans.push_back(1);
cur.push_back({v.s,str[v.s]});
}
else{
ans.push_back(0);
cur.push_back({v.f,str[v.f]});
}
}
sort(all(cur));
int cnt=0;
bool tf=true;
for(int i=0;i<n;i++){
if(cur[i].s=='('){
cnt++;
}
else{
cnt--;
}
if(cnt<0){
tf=false;
break;
}
}
if(tf and cnt==0){
for(auto v:ans){
cout<<v<<' ';
}
cout<<'\n';
return;
}
}
cout<<-1<<'\n';
return;
}
else if(tf2){
int left=0;
int right=0;
vector<pair<int,int>> pos;
vector<pair<int,char>> newpos;
vector<int> ans(n);
for(int i=0;i<n;i++){
auto v=pairs[i];
if(str[v.f]==str[v.s]){
if(str[v.f]=='(') left++;
else right++;
newpos.push_back({v.f,str[v.f]});
ans[i]=0;
}
else{
pos.push_back({v.f,i});
}
}
if(right>n/2 or left>n/2){
cout<<-1<<'\n';
return ;
}
sort(all(pos));
for(int i=0;i<n/2-left;i++){
int id=pos[i].s;
if(str[pairs[id].f]=='(') ans[id]=0;
else ans[id]=1;
newpos.push_back({pos[i].f,'('});
}
for(int i=n/2-left;i<pos.size();i++){
int id=pos[i].s;
if(str[pairs[id].f]==')') ans[id]=0;
else ans[id]=1;
newpos.push_back({pos[i].f,')'});
}
sort(all(newpos));
int cnt=0;
bool tff=true;
for(auto v:newpos){
if(v.s=='(') cnt++;
else cnt--;
if(cnt<0){
tff=false;
break;
}
}
if(!tff or cnt!=0){
cout<<-1<<'\n';
return;
}
for(int i=0;i<n;i++){
cout<<ans[i]<<' ';
}
cout<<'\n';
return;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t--) solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:99:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i=n/2-left;i<pos.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
501 ms |
684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
501 ms |
684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
