Submission #209609

#	Time	Username	Problem	Language	Result	Execution time	Memory
209609		stefdasca	Port Facility (JOI17_port_facility)	C++14	10 / 100	624 ms	380 KiB

port_facility

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    int x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_seed()
{
    long long a = rng();
    return a;
}

pair<int, int> bk[1000002];
int n, ways;
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);



    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> bk[i].fi >> bk[i].se;
    sort(bk, bk + n);
    for(int i = 0; i < (1<<n); ++i)
    {
        vector<int> v[3];
        bool valid = 1;
        for(int j = 0; j < n; ++j)
        {
            while(!v[1].empty() && v[1].back() < bk[j].fi)
                v[1].pop_back();
            while(!v[2].empty() && v[2].back() < bk[j].fi)
                v[2].pop_back();
            if(i & (1<<j))
            {
                if(v[1].empty() || v[1].back() > bk[j].se)
                    v[1].pb(bk[j].se);
                else
                {
                    valid = 0;
                    break;
                }
            }
            else
            {
                if(v[2].empty() || v[2].back() > bk[j].se)
                    v[2].pb(bk[j].se);
                else
                {
                    valid = 0;
                    break;
                }
            }
        }
        ways += valid;
    }
    int p2 = 1;
    while(p2 < ways)
        p2 *= 2;
    assert(ways == 0 || p2 == ways);
    cout << ways;
    return 0;
}

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