Submission #1194488

#TimeUsernameProblemLanguageResultExecution timeMemory
1194488omarrrrPort Facility (JOI17_port_facility)C++20
10 / 100
195 ms592 KiB
#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";


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...