oj.uz

답안 #704998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704998 2023-03-03T07:43:51 Z guagua0407 Superpozicija (COCI22_superpozicija) C++17
0 / 110
 24 ms 340 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;
    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<pair<int,char>> newpos;
        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++;
                newpos.push_back({v.f,str[v.f]});
                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;
            newpos.push_back({pos[i].f,'('});
        }
        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;
            newpos.push_back({pos[i].f,')'});
        }
        sort(all(newpos));
        int cnt=0;
        bool tff=true;
        for(auto v:newpos){
            if(v.s=='(') cnt++;
            else cnt--;

            if(cnt<0){
                tff=false;
                break;
            }
        }
        if(!tff or cnt!=0){
            cout<<-1<<'\n';
            return;
        }
        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:103: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]
  103 |         for(int i=n/2-left;i<pos.size();i++){
      |                            ~^~~~~~~~~~~
Main.cpp:25:10: warning: variable 'tf2' set but not used [-Wunused-but-set-variable]
   25 |     bool tf2=true;
      |          ^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -