oj.uz

Submission #704985

# Submission time Handle Problem Language Result Execution time Memory
704985 2023-03-03T07:36:18 Z guagua0407 Superpozicija (COCI22_superpozicija) C++17
0 / 110
 478 ms 548 KB 
#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 tf2=true;
    for(auto v:pairs){
        tf2|=(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(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]=='(') right++;
                else left++;
                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

Main.cpp: In function 'void solve()':
Main.cpp:96: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]
   96 |         for(int i=n/2-left;i<pos.size();i++){
      |                            ~^~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 324 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

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