oj.uz

Submission #766831

# Submission time Handle Problem Language Result Execution time Memory
766831 2023-06-26T07:59:17 Z dimash241 Passport (JOI23_passport) C++17
16 / 100
 160 ms 230184 KB 
#include <cstdio>
#include <random>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <chrono>


#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

// вправо, вниз, влево, вверх
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

// ход конем
//int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
//int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::system_clock::now().time_since_epoch().count());
int rndInteger (int l, int r) {
    return uniform_int_distribution<int> (l, r)(rnd);
}

const int MOD = (int) 998244353;
const int N = (int) 300+7;

int n, q;
int L[N], R[N];
int ans[N], x[N];
int dp[N][N][N];

int solve(int l, int r, int pass) {
    if(l == 1 && r == n) {
        return 1;
    }
    int &res = dp[l][r][pass];
    if(res != -1) return res;
    res = 1e9;

    for (int p = l; p <= r; ++p) {
        int nl = min(l, L[p]);
        int nr = max(r, R[p]);

        if(nl != l || nr != r) {
            res = min(res, solve(nl, nr, p) + 1);
        }
    }

    return res;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> L[i] >> R[i];

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> x[i];
        memset(dp, -1, sizeof dp);
        int res = solve(L[x[i]], R[x[i]], x[i]);
        if(res > n) res = -1;
        cout << res << '\n';
    }

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 113516 KB Output is correct
2 Correct 38 ms 113464 KB Output is correct
3 Correct 44 ms 113484 KB Output is correct
4 Runtime error 147 ms 230084 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 113528 KB Output is correct
2 Correct 43 ms 113536 KB Output is correct
3 Correct 40 ms 113508 KB Output is correct
4 Correct 40 ms 113456 KB Output is correct
5 Correct 45 ms 113452 KB Output is correct
6 Correct 39 ms 113448 KB Output is correct
7 Correct 38 ms 113452 KB Output is correct
8 Correct 38 ms 113456 KB Output is correct
9 Correct 39 ms 113448 KB Output is correct
10 Correct 39 ms 113492 KB Output is correct
11 Correct 45 ms 113492 KB Output is correct
12 Correct 51 ms 113576 KB Output is correct
13 Correct 41 ms 113500 KB Output is correct
14 Correct 40 ms 113456 KB Output is correct
15 Correct 43 ms 113584 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 113528 KB Output is correct
2 Correct 43 ms 113536 KB Output is correct
3 Correct 40 ms 113508 KB Output is correct
4 Correct 40 ms 113456 KB Output is correct
5 Correct 45 ms 113452 KB Output is correct
6 Correct 39 ms 113448 KB Output is correct
7 Correct 38 ms 113452 KB Output is correct
8 Correct 38 ms 113456 KB Output is correct
9 Correct 39 ms 113448 KB Output is correct
10 Correct 39 ms 113492 KB Output is correct
11 Correct 45 ms 113492 KB Output is correct
12 Correct 51 ms 113576 KB Output is correct
13 Correct 41 ms 113500 KB Output is correct
14 Correct 40 ms 113456 KB Output is correct
15 Correct 43 ms 113584 KB Output is correct
16 Runtime error 160 ms 230184 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 113528 KB Output is correct
2 Correct 43 ms 113536 KB Output is correct
3 Correct 40 ms 113508 KB Output is correct
4 Correct 40 ms 113456 KB Output is correct
5 Correct 45 ms 113452 KB Output is correct
6 Correct 39 ms 113448 KB Output is correct
7 Correct 38 ms 113452 KB Output is correct
8 Correct 38 ms 113456 KB Output is correct
9 Correct 39 ms 113448 KB Output is correct
10 Correct 39 ms 113492 KB Output is correct
11 Correct 45 ms 113492 KB Output is correct
12 Correct 51 ms 113576 KB Output is correct
13 Correct 41 ms 113500 KB Output is correct
14 Correct 40 ms 113456 KB Output is correct
15 Correct 43 ms 113584 KB Output is correct
16 Runtime error 160 ms 230184 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 113516 KB Output is correct
2 Correct 38 ms 113464 KB Output is correct
3 Correct 44 ms 113484 KB Output is correct
4 Runtime error 147 ms 230084 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -