| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1113958 | lucascgar | 밀림 점프 (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
/*
se eu tenho um cara da esquerda sempre vale pegar primeiro cara que der da direita
se eu tenho um destino na direita sempre vale pegar o maior cara da esquerda q chega la
nenhuma subtituição nos intervalos muda nada pq
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 2e5+10, MAXQ = 1e5+10, BIG = 1e9+8;
int n, h[MAXN], ds[MAXN];
int r[MAXN], l[MAXN];
bool thing = 0;
void init(int N, vector<int> H){
n = N;
thing = 1;
for (int i=0;i<n;i++){
h[i] = H[i];
if (h[i]!=i+1) thing=0;
}
if (thing) return;
for (int i=0;i<n;i++){
r[i] = l[i] = -1;
for (int j=i+1;j<n;j++) if (h[i]<h[j]){
r[i] = j;
break;
}
for (int j=i-1;j>=0;j--) if (h[i]<h[j]){
l[i]=j;
break;
}
}
}
int minimum_jumps(int A, int B, int C, int D){ // A <= B < C <= D
if (thing){
return C-B;
}
int ans = BIG;
for (int i=A;i<=B;i++){
vector<int> ds(n, -1);
queue<int> q;
q.push(i);
ds[i]=0;
while (!q.empty()){
int u = q.front();
if (u>=C && u<=D){
ans = ds[u];
break;
}
q.pop();
if (l[u] != -1 && ds[l[u]]==-1){
ds[l[u]] = ds[u]+1;
q.push(l[u]);
}
if (r[u] != -1 && ds[r[u]]==-1){
ds[r[u]] = ds[u]+1;
q.push(r[u]);
}
}
}
if (ans==BIG) return -1;
return ans;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
init(7, {3, 2, 1, 6, 4, 5, 7});
cout << minimum_jumps(4, 4, 6, 6) << '\n';
cout << minimum_jumps(1, 3, 5, 6) << '\n';
cout << minimum_jumps(0, 1, 2, 2) << '\n';
return 0;
}