Submission #566696

#TimeUsernameProblemLanguageResultExecution timeMemory
566696Ooops_sorryRainforest Jumps (APIO21_jumps)C++14
33 / 100
4045 ms5064 KiB
#include<bits/stdc++.h> #ifndef LOCAL #include "jumps.h" #endif #define ld long double #define ll long long #define pb push_back using namespace std; const int INF = 1e9; mt19937 rnd(51); int n; vector<int> h, l, r; void init(int N, std::vector<int> H) { h = H; n = N; l.clear(), r.clear(); l.resize(n, -1); r.resize(n, n); deque<int> q; for (int i = 0; i < n; i++) { while (q.size() > 0 && h[q.back()] < h[i]) { r[q.back()] = i; q.pop_back(); } q.pb(i); } q.clear(); for (int i = n - 1; i >= 0; i--) { while (q.size() > 0 && h[q.back()] < h[i]) { l[q.back()] = i; q.pop_back(); } q.pb(i); } } int minimum_jumps(int a, int b, int c, int d) { int j = c, k = -1; for (int i = c; i <= d; i++) { if (h[i] > h[j]) { j = i; } } for (int i = b; i >= a && h[i] < h[j]; i--) { if (k == -1 || h[i] > h[k]) { k = i; } } if (k == -1) return -1; int cnt = 1; while (r[k] < c) { int L = l[k], R = r[k]; cnt++; if (L == -1) { k = R; } else if (R == -1) { k = L; } else { if (h[L] > h[R] && h[L] < h[j]) { k = L; } else { k = R; } } } if (r[k] > d) return -1; return cnt; } #ifdef LOCAL int my_solve(int a, int b, int c, int d) { map<int,int> dist; deque<int> q; for (int i = a; i <= b; i++) { dist[i] = 0; q.pb(i); } while (q.size() > 0) { int v = q.front(); if (c <= v && v <= d) return dist[v]; q.pop_front(); int L = l[v], R = r[v]; if (L != -1 && dist.find(L) == dist.end()) { dist[L] = dist[v] + 1; q.pb(L); } if (R != n && dist.find(R) == dist.end()) { dist[R] = dist[v] + 1; q.pb(R); } } return -1; } int main() { while (1) { int n = rnd() % 10 + 1, q = rnd() % 10 + 1; vector<int> h(n); iota(h.begin(), h.end(), 1); shuffle(h.begin(), h.end(), rnd); init(n, h); cout << n << endl; for (auto to : h) { cout << to << ' '; } cout << endl; for (int i = 0; i < q; i++) { vector<int> arr(4); for (int j = 0; j < 4; j++) arr[j] = rnd() % n; sort(arr.begin(), arr.end()); if (arr[1] >= arr[2]) continue; cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << ' ' << arr[3] << endl; auto res = minimum_jumps(arr[0], arr[1], arr[2], arr[3]), res2 = my_solve(arr[0], arr[1], arr[2], arr[3]); if (res != res2) { cout << "BAD" << endl; cout << res << ' ' << res2 << endl; return 0; } } } } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...