oj.uz

Submission #1062346

# Submission time Handle Problem Language Result Execution time Memory
1062346 2024-08-17T03:38:53 Z huutuan Superpozicija (COCI22_superpozicija) C++14
0 / 110
 14 ms 4444 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], id[N];

bool check(string t){
   int pf=0;
   for (char c:t){
      if (c=='(') ++pf;
      else --pf;
      if (pf<0) return 0;
   }
   return pf==0;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int t; cin >> t;
   while (t--){
      cin >> n >> s;
      s=" "+s;
      int cnt1=0, cnt2=0;
      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;
         id[a[i].first]=id[a[i].second]=i;
         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) pq.emplace(p[i], i);
         pf+=d[i];
         if (pf<0){
            if (pq.empty()) break;
            auto t=pq.top(); pq.pop();
            ans[t.second]^=1;
            if (t.first<=i) pf+=2;
            else ++pf, ++d[t.first];
         }
      }
      if (pf) cout << -1 << '\n';
      else{
         for (int i=1; i<=n; ++i) cout << ans[i] << " \n"[i==n];
      }
   }
   return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:29:11: warning: unused variable 'cnt1' [-Wunused-variable]
   29 |       int cnt1=0, cnt2=0;
      |           ^~~~
Main.cpp:29:19: warning: unused variable 'cnt2' [-Wunused-variable]
   29 |       int cnt1=0, cnt2=0;
      |                   ^~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 70.0

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