Submission #704971

#	Time	Username	Problem	Language	Result	Execution time	Memory
704971		guagua0407	Superpozicija (COCI22_superpozicija)	C++17	0 / 110	463 ms	332 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

void solve(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    vector<pair<int,int>> pairs;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        pairs.push_back({a,b});
    }
    /*bool tf=true;
    for(auto v:pairs){
        tf|=(v.f+1==v.s);
    }*/
    if(n<=10){
        if(n&1){
            cout<<-1<<'\n';
            return;
        }
        for(int i=0;i<(1<<n);i++){
            vector<pair<int,int>> cur;
            vector<int> ans;
            for(int j=0;j<n;j++){
                auto v=pairs[j];
                if(i&(1<<j)){
                    ans.push_back(1);
                    cur.push_back({v.s,str[v.s]});
                }
                else{
                    ans.push_back(0);
                    cur.push_back({v.f,str[v.f]});
                }
            }
            sort(all(cur));
            int cnt=0;
            bool tf=true;
            for(int i=0;i<n;i++){
                if(cur[i].s=='('){
                    cnt++;
                }
                else{
                    cnt--;
                }
                if(cnt<0){
                    tf=false;
                    break;
                }
            }
            if(tf and cnt==0){
                for(auto v:ans){
                    cout<<v<<' ';
                }
                cout<<'\n';
                return;
            }
        }
        cout<<-1<<'\n';
        return;
    }
    /*else if(tf){
        int left=0;
        int right=0;
        vector<int> pos;
        for(auto v:pairs){
            if(str[v.f]==str[v.s]){
                if(str[v.f]=='(') right++;
                else left++;
            }
            else{
            }
        }
        if(right>n/2 or left>n/2){
            cout<<-1;
            return ;
        }
        
    }*/
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
}

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