제출 #1194488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194488		omarrrr	Port Facility (JOI17_port_facility)	C++20	10 / 100	195 ms	592 KiB

port_facility

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back

using namespace std;

ll const N=1e6 + 10,mod=1e9 + 7;
ll n,a,b,c;

vector<pair<ll,ll>>v;

bool valid(vector<ll>a){

    for(ll i=0;i<a.size();i++){
        for(ll j=i+1;j<a.size();j++){
            if(v[a[j]].F<v[a[i]].S && v[a[j]].S>v[a[i]].S)
                return false;
        }
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    v.resize(n);
    for(ll i=0;i<n;i++){
        cin>>v[i].F>>v[i].S;
    }
    sort(v.begin(),v.end());
//    for(ll i=0;i<n;i++){
//        cout<<v[i].F<<" "<<v[i].S<<"\n";
//    }
//    cout<<"\n";
    vector<ll>a,b;
    ll res=0;
    for(ll i=0;i<(1<<n);i++){
        a.clear();
        b.clear();
        for(ll j=0;j<n;j++){
            if(i&(1<<j)){
                a.pb(j);
            }else{
                b.pb(j);
            }
        }
        if(valid(a) && valid(b)){
            res++;
            res%=mod;
//            for(ll j=0;j<a.size();j++){
//                cout<<a[j]<<" ";
//            }
//            cout<<"aa\n";
//            for(ll j=0;j<b.size();j++){
//                cout<<b[j]<<" ";
//            }
//            cout<<"bb\n";

        }
    }
    cout<<res<<"\n";


}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22