제출 #1125410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125410		SalihSahin	Superpozicija (COCI22_superpozicija)	C++20	30 / 110	61 ms	5456 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int mod = 998244353;
const int N = 1e5 + 10;
const int inf = 1e17;


int32_t main(){
  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<pair<int, int> > p(n);
    for(int i = 0; i < n; i++){
        cin>>p[i].first>>p[i].second;
        p[i].first--;
        p[i].second--;
    }

    if(n&1){
        cout<<-1<<endl;
        continue;
    }

    int delt = 0;
    vector<int> ans(n, -1);
    vector<array<int, 3> > can;
    for(int i = 0; i < n; i++){
        if(s[p[i].first] == '(' && s[p[i].second] == '('){
            ans[i] = 0;
            delt++;
        }
        if(s[p[i].first] == ')' && s[p[i].second] == ')'){
            ans[i] = 1;
            delt--;
        }

        if(s[p[i].first] == '(' && s[p[i].second] == ')'){
            can.pb({p[i].first, p[i].second, i+1});
        }
        if(s[p[i].first] == ')' && s[p[i].second] == '('){
            can.pb({p[i].second, p[i].first, -(i+1)});
        }
    }
    sort(can.begin(), can.end());
    int x = can.size();
    int take = 0;
    if(delt < 0){
        take -= delt;
        x -= take;
        delt = 0;
    }
    if(delt > 0){
        x -= delt;
        delt = 0;
    }
    take += x/2;

    for(int i = 0; i < can.size(); i++){
        if(i < take){
            if(can[i][2] < 0) ans[-can[i][2] - 1] = 1;
            else ans[can[i][2]-1] = 0;
        }
        else{
            if(can[i][2] < 0) ans[-can[i][2] - 1] = 0;
            else ans[can[i][2]-1] = 1;
        }
    }

    vector<int> taken;
    for(int i = 0; i < n; i++){
        if(ans[i] == 0) taken.pb(p[i].first);
        else taken.pb(p[i].second);
    }
    sort(taken.begin(), taken.end());

    int check = 1, val = 0;
    for(auto itr: taken){
        if(s[itr] == '(') val++;
        else val--;

        if(val < 0) check = 0;
    }
    if(val > 0) check = 0;

    if(!check){
        cout<<-1<<endl;
    }
    else{
        for(int i = 0; i < n; i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
  }
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 70