oj.uz

Submission #1062349

# Submission time Handle Problem Language Result Execution time Memory
1062349 2024-08-17T03:42:47 Z huutuan Superpozicija (COCI22_superpozicija) C++14
10 / 110
 18 ms 3636 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+10;
int n;
string s;
int p[N];
pair<int, int> a[N];
int ans[N], d[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int t; cin >> t;
   while (t--){
      cin >> n >> s;
      s=" "+s;
      vector<int> vv;
      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
      for (int i=1; i<=n; ++i){
         cin >> a[i].first >> a[i].second;
         p[a[i].first]=a[i].second;
         p[a[i].second]=a[i].first;
         if (s[a[i].first]==s[a[i].second]){
            if (s[a[i].first]=='('){
               ans[i]=0;
               ++d[a[i].first];
            }else{
               ans[i]=1;
               --d[a[i].second];
            }
         }else{
            if (s[a[i].first]=='('){
               ans[i]=1;
               --d[a[i].second];
            }else{
               ans[i]=0;
               --d[a[i].first];
            }
         }
      }
      int pf=0;
      for (int i=1; i<=n*2; ++i){
         if (p[i]>i && s[i]!=s[p[i]]) pq.emplace(p[i], i);
         pf+=d[i];
         if (pf<0){
            if (pq.empty()) break;
            auto tt=pq.top(); pq.pop();
            ans[tt.second]^=1;
            if (tt.first<=i) pf+=2;
            else ++pf, ++d[tt.first];
         }
      }
      if (pf) cout << -1 << '\n';
      else{
         for (int i=1; i<=n; ++i) cout << ans[i] << " \n"[i==n];
      }
      for (int i=1; i<=n*2; ++i) d[i]=0;
   }
   return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2392 KB Output is correct
2 Correct 11 ms 2652 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 12 ms 2908 KB Output is correct
5 Correct 10 ms 3156 KB Output is correct
6 Correct 7 ms 3304 KB Output is correct
7 Correct 13 ms 3400 KB Output is correct
8 Correct 11 ms 3416 KB Output is correct
9 Correct 11 ms 3452 KB Output is correct
10 Correct 15 ms 3636 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2656 KB Output isn't correct
2 Halted 0 ms 0 KB -