# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
810571 | bonk | Superpozicija (COCI22_superpozicija) | C++14 | 382 ms | 3024 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
vector<pair<int, int>>v;
bool valid(string s){
int sum = 0;
for(int i = 0; i < s.length(); i++){
if(s[i] == '(') sum++;
else{
sum--;
if(sum < 0) return false;
}
}
return (sum == 0);
}
void st1(){
for(int i = 0; i < n; i++){
cin >> v[i].first >> v[i].second;
v[i].first--;
v[i].second--;
}
int all = (1<<n);
bool ok = false;
for(int mask = 0; mask < all; mask++){
if(ok) break;
string cur = "";
vector<int>tmp;
for(int j = 0; j < n; j++){
if((mask>>j)&1){
tmp.push_back(v[j].second);
} else{
tmp.push_back(v[j].first);
}
}
sort(tmp.begin(), tmp.end());
for(auto &x: tmp) cur += s[x];
if(valid(cur)){
ok = true;
for(int j = 0; j < n; j++){
cout << ((mask>>j)&1) << " ";
}
cout << '\n';
}
}
if(!ok) cout << -1 << '\n';
return;
}
void solve(){
cin >> n;
cin >> s;
v.resize(n);
if(n <= 10){
st1();
return;
}
string cur = "";
vector<int>tmp;
for(int i = 0; i < n; i++){
cin >> v[i].first >> v[i].second;
v[i].first--; v[i].second--;
if(s[v[i].first] == '(') tmp.push_back(v[i].first);
else tmp.push_back(v[i].second);
}
sort(tmp.begin(), tmp.end());
for(auto &x: tmp) cur += s[x];
if(valid(cur)){
for(int i = 0; i < n; i++){
if(s[v[i].first] == '(') cout << 0 << ' ';
else cout << 1 << ' ';
}
cout << '\n';
} else{
cout << -1 << '\n';
}
return;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while(tc--){
solve();
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |