Submission #897978

#	Time	Username	Problem	Language	Result	Execution time	Memory
897978		vjudge1	Passport (JOI23_passport)	C++17	46 / 100	1547 ms	25172 KiB

passport

// MDSPro
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const ld PI = 3.141592653589793;
const int MOD = 1e9+7;
const int INF = 1e9;
const ll INFLL = 4e18;
const double EPS = 1e-9;
const int MAXN = 1000*1007;

void solve(int NT){
    int n; cin >> n;
    vector<pair<int, int>> v = {{0, 0}};
    for(int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        v.emplace_back(x, y);
    }

    int q; cin >> q;
    int x; cin >> x;
    if(x == 1) {
        vector<int> opening(n + 1, 0);
        for(int i = 1; i <= n; ++i) {
            opening[i] = max(opening[i], v[i].second);
        }

        int cur = 0, til = 1, ans = 0;
        while(til < n) {
            int ntil = til;
            for(int i = cur + 1; i <= til; ++i) {
                ntil = max(ntil, opening[i]);
            }

            if(ntil == til) break;
            cur = til;
            til = ntil;
            ans++;
        }
        if(til != n) ans = -1;
        cout << ans;
    } else {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
        dp[x][x] = 0;
        for(int r = 1; r <= n; ++r) {
            for(int l = r; l >= 1; --l) {
                if(dp[l][r] != INF) {
                    for(int m = l; m <= r; ++m) {
                        int nl = min(l, v[m].first);
                        int nr = max(r, v[m].second);
                        if(nl != l || r != nr) {
                            dp[nl][nr] = min(dp[nl][nr], dp[l][r] + 1);
                        } 
                    }
                }
            }
        }

        if(dp[1][n] == INF) dp[1][n] = -1;
        cout << dp[1][n];
    }
}

// #define TESTCASES
int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t = 1;
    #ifdef TESTCASES
        cin >> t;
    #endif
    
    for(int i = 1; i <= t; ++i){
        solve(i);
        cout << "\n";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46