Submission #704953

#TimeUsernameProblemLanguageResultExecution timeMemory
704953Paul_Liao_1457Superpozicija (COCI22_superpozicija)C++17
0 / 110
153 ms472 KiB
//記得跳題 //#pragma GCC optimize("O4,unroll_loops") //#pragma GCC target("avx2") #include<iostream> #include<array> #include<vector> #include<string> #include<algorithm> #include<set> #include<queue> #include<stack> #include<math.h> #include<map> #include<unordered_map> #include<unordered_set> #include<cstring> #include<iomanip> #include<bitset> #include<tuple> #include<random> #define ll long long #define FOR(i,a,b) for(int i=a;i<b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) #define pb push_back #define INF (ll)(2e18) #define F first #define S second #define endl "\n" #define AC ios::sync_with_stdio(0); using namespace std; string s; int id[200005], a[200005], b[200005], suf[200005], ans[200005], who[200005]; void solve() { int n; cin >> n; cin >> s; int ca = 0; FOR (i, 0, n) { cin >> a[i] >> b[i]; a[i]--; b[i]--; id[a[i]] = 1; id[b[i]] = 2; if (s[a[i]] != s[b[i]]) ca = 1; } ca = 1; if (!ca) { int cnt = 0; FOR (i, 0, 2*n) { if (s[i] == '(') cnt++; else cnt --; } if (cnt) { cout << -1 << endl; } else { int cur = 0; FOR (i, 0, 2*n) { if (s[i] == '(' && id[i] == 1) { cur++; } else if(s[i] == ')' && id[i] == 2) { cur--; if (cur < 0) { cout << -1 << endl; return; } } } FOR (i, 0, n) { if (s[a[i]] == '(') cout << 0 << " "; else cout << 1 << " "; } cout << endl; } } else if(n <= 10) { string tmp = s; FOR (m, 0, 1<<n) { FOR (i, 0, n) { if (m & (1<<i)) { tmp[a[i]] = s[a[i]]; tmp[b[i]] = '?'; } else { tmp[a[i]] = '?'; tmp[b[i]] = s[b[i]]; } } // cout << "tmp = " << tmp << endl; bool ok = 1; int sum = 0; FOR (i, 0, 2*n) { if (tmp[i] != '?') { if (tmp[i] == '(') sum++; else sum--; if (sum < 0){ ok = 0; break; } } } if (ok && sum == 0) { FOR (i, 0, n) { if (m & (1<<i)) { cout << 0 << " "; } else { cout << 1 << " "; } } cout << endl; return; } } cout << -1 << endl; } else { FOR (i, 0, n) { ans[i] = 0; who[a[i] / 2] = i; } suf[n] = 0; REP (i, n-1, 0) { suf[i] = suf[i+1]; if (s[2*i] == ')' || s[2*i+1] == ')') suf[i]++; } int sum = 0; FOR (i, 0, n) { if (s[2*i] == s[2*i+1]) { if (s[2*i] == '(') sum++; else sum--; if (sum < 0) { cout << -1 << endl; return; } } else { if (suf[i+1] >= sum + 1) { sum++; if (s[2*i] == '(') ans[who[i]] = 0; else ans[who[i]] = 1; } else { sum--; if (s[2*i] == '(') ans[who[i]] = 1; else ans[who[i]] = 0; if (sum < 0) { cout << -1 << endl; return; } } } } if (sum) { cout << -1 << endl; } else { FOR (i, 0, n) cout << ans[i] << " "; cout << endl; } } } signed main(){ AC; int t; cin >> t; while (t--) { solve(); } } /* vector<pair<int, int> > e[200005]; vector<pair<int, int> > ans; void dfs(int now, int f,int up){ if (up != -1) { ans.pb({now, up}); } for (auto i:e[now]) if (i.F != f) { dfs(i.F, now, i.S); } } signed main(){ AC; int n, m; cin >> n >> m; FOR (i, 0, m) { int a, b; cin >> a >> b; e[a].pb({b, 0}); e[b].pb({a, 1}); } dfs(1, 0, -1); cout << ans.size() << endl; for (auto i:ans) { cout << i.F << " " << i.S << endl; } } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...