| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 874176 | 2023-11-16T11:55:59 Z | LucaLucaM | Passport (JOI23_passport) | C++17 | 25 ms | 4564 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby
typedef long long ll;
/**
ce cred eu ca se intampla defapt e ca mereu voi putea accesa un interval de tari
si atunci o sa am o dinamica de genu
dp[i][l] =def= care e cel mai din dreapta r la care pot ajunge dupa i operatii, a.i. am capatul din stanga pe pozitia l
asta pare greu de optimizat
dp[l][r] =def= #min de operatii ca sa ajung cu capatul stanga in l si capatul dreapta in r
**/
struct Country {
int l, r;
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<Country> v(n + 1);
int rMax[n + 1] = {};
for (int i = 1; i <= n; i++) {
std::cin >> v[i].l >> v[i].r;
rMax[i] = std::max(rMax[i - 1], v[i].r);
}
int q;
std::cin >> q;
while (q--) {
int x;
std::cin >> x;
if (x == 1) {
int answer = 0;
while (x != n && rMax[x] > x) {
x = rMax[x];
answer++;
}
if (x != n) {
answer = -1;
}
std::cout << answer << '\n';
} else {
int dp[n + 1][n + 1];
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
dp[l][r] = 1e9;
}
}
dp[x][x] = 0;
for (int l = x; l > 0; l--) {
for (int r = l; r <= n; r++) {
for (int j : {l, r}) {
int newL = std::min(l, v[j].l);
int newR = std::max(r, v[j].r);
dp[newL][newR] = std::min(dp[newL][newR], dp[l][r] + 1);
}
}
}
std::cout << (dp[1][n] == 1e9? -1 : dp[1][n]) << '\n';
}
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Correct | 0 ms | 348 KB | Output is correct |
| 4 | Correct | 25 ms | 4416 KB | Output is correct |
| 5 | Correct | 24 ms | 4444 KB | Output is correct |
| 6 | Correct | 25 ms | 4564 KB | Output is correct |
| 7 | Correct | 20 ms | 3932 KB | Output is correct |
| 8 | Correct | 17 ms | 3336 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Correct | 0 ms | 348 KB | Output is correct |
| 4 | Correct | 0 ms | 348 KB | Output is correct |
| 5 | Correct | 0 ms | 348 KB | Output is correct |
| 6 | Correct | 0 ms | 348 KB | Output is correct |
| 7 | Correct | 0 ms | 456 KB | Output is correct |
| 8 | Correct | 1 ms | 348 KB | Output is correct |
| 9 | Incorrect | 0 ms | 348 KB | Output isn't correct |
| 10 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Correct | 0 ms | 348 KB | Output is correct |
| 4 | Correct | 0 ms | 348 KB | Output is correct |
| 5 | Correct | 0 ms | 348 KB | Output is correct |
| 6 | Correct | 0 ms | 348 KB | Output is correct |
| 7 | Correct | 0 ms | 456 KB | Output is correct |
| 8 | Correct | 1 ms | 348 KB | Output is correct |
| 9 | Incorrect | 0 ms | 348 KB | Output isn't correct |
| 10 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Correct | 0 ms | 348 KB | Output is correct |
| 4 | Correct | 0 ms | 348 KB | Output is correct |
| 5 | Correct | 0 ms | 348 KB | Output is correct |
| 6 | Correct | 0 ms | 348 KB | Output is correct |
| 7 | Correct | 0 ms | 456 KB | Output is correct |
| 8 | Correct | 1 ms | 348 KB | Output is correct |
| 9 | Incorrect | 0 ms | 348 KB | Output isn't correct |
| 10 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Correct | 0 ms | 348 KB | Output is correct |
| 4 | Correct | 25 ms | 4416 KB | Output is correct |
| 5 | Correct | 24 ms | 4444 KB | Output is correct |
| 6 | Correct | 25 ms | 4564 KB | Output is correct |
| 7 | Correct | 20 ms | 3932 KB | Output is correct |
| 8 | Correct | 17 ms | 3336 KB | Output is correct |
| 9 | Correct | 0 ms | 344 KB | Output is correct |
| 10 | Correct | 0 ms | 348 KB | Output is correct |
| 11 | Correct | 0 ms | 348 KB | Output is correct |
| 12 | Correct | 0 ms | 348 KB | Output is correct |
| 13 | Correct | 0 ms | 348 KB | Output is correct |
| 14 | Correct | 0 ms | 348 KB | Output is correct |
| 15 | Correct | 0 ms | 456 KB | Output is correct |
| 16 | Correct | 1 ms | 348 KB | Output is correct |
| 17 | Incorrect | 0 ms | 348 KB | Output isn't correct |
| 18 | Halted | 0 ms | 0 KB | - |