제출 #902243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
902243		efedmrlr	밀림 점프 (APIO21_jumps)	C++17	33 / 100	4069 ms	14556 KiB

jumps

#include "jumps.h"

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)



void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q;

vector<array<int,2> > adj;

void init(int N, std::vector<int> H) {
  vector<array<int,2> > srt(N);
  set<int> st;
  n = N;
  adj.assign(N, array<int,2>({-1,-1}) );
  REP(i,N) {
    srt[i] = {H[i], i};
    st.insert(i);
  }
  sort(srt.begin(), srt.end());
  for(auto c : srt) {
    st.erase(c[1]);
    auto itr = st.lower_bound(c[1]);
    if(st.size() == 0) break;
    if(itr != st.end()) {
      adj[c[1]][1] = *itr;
    }
    if(itr != st.begin()) {
      itr--;
      adj[c[1]][0] = *itr;
    }

  }
}

int minimum_jumps(int A, int B, int C, int D) {
  queue<int> que;
  vector<int> vis(n, 0);
  for(int i = A; i<=B; i++) {
    que.push(i);
    vis[i] = 1; 
  }
  int dist = 0;
  que.push(-1);
  
  while(que.size() > 1) {
    int cur = que.front();
    que.pop();
    if(cur == -1) {
      dist++;
      que.push(-1);
      continue;
    }
    if(C <= cur && cur <= D) {
      return dist;
    }
    
    for(auto c : adj[cur]) {
      if(c == -1 || vis[c]) continue;
      vis[c] = 1;
      que.push(c);
    }
  }
  return -1;
}

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19