Submission #704989

#	Time	Username	Problem	Language	Result	Execution time	Memory
704989		guagua0407	Superpozicija (COCI22_superpozicija)	C++17	0 / 110	14 ms	212 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;
    if(n&1){
        cout<<-1<<'\n';
        return;
    }
    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 tf2=true;
    for(auto v:pairs){
        if((v.f+1)!=v.s) tf2=false;
    }
    /*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;
    }*/
    if(tf2){
        int left=0;
        int right=0;
        vector<pair<int,int>> pos;
        vector<int> ans(n);
        for(int i=0;i<n;i++){
            auto v=pairs[i];
            if(str[v.f]==str[v.s]){
                if(str[v.f]=='(') left++;
                else right++;
                ans[i]=0;
            }
            else{
                pos.push_back({v.f,i});
            }
        }
        if(right>n/2 or left>n/2){
            cout<<-1<<'\n';
            return ;
        }
        sort(all(pos));
        for(int i=0;i<n/2-left;i++){
            int id=pos[i].s;
            if(str[pairs[id].f]=='(') ans[id]=0;
            else ans[id]=1;
        }
        for(int i=n/2-left;i<pos.size();i++){
            int id=pos[i].s;
            if(str[pairs[id].f]==')') ans[id]=0;
            else ans[id]=1;
        }
        for(int i=0;i<n;i++){
            cout<<ans[i]<<' ';
        }
        cout<<'\n';
        return;
    }
}

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

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:100:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i=n/2-left;i<pos.size();i++){
      |                            ~^~~~~~~~~~~

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