Submission #704945

#TimeUsernameProblemLanguageResultExecution timeMemory
704945browntoadSuperpozicija (COCI22_superpozicija)C++14
0 / 110
5 ms6868 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define FOR(i, a, b) for (int i=(a); i<(b); i++) #define REP(i, n) FOR(i, 0, n) #define REP1(i, n) FOR(i, 1, n+1) #define RREP(i, n) for (int i=(n)-1; i>=0; i--) #define pii pair<int, int> #define f first #define s second #define pb push_back #define ALL(x) (x).begin(), (x).end() #define SZ(x) (int)((x).size()) const int maxn = 2e5+5; int n; string str; vector<pii> op(maxn); bool typ = 1; void inp(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n; cin>>str; REP(i, n){ cin>>op[i].f>>op[i].s; op[i].f--; op[i].s--; if (op[i].s != op[i].f+1) typ = 0; } } void solve0(){ assert(0); if (n%2){ cout<<-1<<endl; return; } } void solve1(){ if (n%2){ cout<<-1<<endl; return; } vector<int> fans(n); int cl = 0, cr = 0; REP(i, n){ assert(op[i].f%2 == 0); if (str[op[i].f] == str[op[i].s]){ if (str[op[i].f] == '('){ fans[op[i].f/2]=1; cl++; } else { fans[op[i].f/2]=-1; cr++; } } } if (cl>n/2 || cr>n/2){ cout<<-1<<endl; return; } int cdelt = 0, fail = 0; REP(i, n){ if (fans[i] == 0){ if (cl < n/2){ cl++; fans[i]=1; cdelt++; } else { fans[i]=-1; cdelt--; } } else cdelt+=fans[i]; if (cdelt < 0) fail=1; } if (cdelt != 0) fail=1; if (fail){ cout<<-1<<endl; return; } else { REP(i, n){ if (str[op[i].f] == str[op[i].s]) cout<<0; else { if (fans[op[i].f/2] == (str[op[i].f] == '(')*2-1) cout<<0; else cout<<1; } if (i!=n-1) cout<<' '; } cout<<endl; } } signed main(){ int t; cin>>t; while(t--){ inp(); if (typ){ solve1(); } else solve0(); typ = 1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...