Submission #1062351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062351		huutuan	Superpozicija (COCI22_superpozicija)	C++14	110 / 110	23 ms	5720 KiB

Main

#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];

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;
         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 && s[i]!=s[p[i]]) pq.emplace(p[i], id[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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 70 / 70