oj.uz

답안 #428764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428764 2021-06-15T14:19:25 Z hhhhaura 밀림 점프 (APIO21_jumps) C++14
0 / 100
 4000 ms 15280 KB 
#define wiwihorz
#include "jumps.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define MOD 1000000007
#define eps (1e-9)
#define INF 1000000000
using namespace std;

#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
void kout() {cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
int n;
vector<int> L, R, d, h;

void init(int N, vector<int> H) {
	n = N, h = H;
	set<int> s; vector<int> a(n, 0);
	L.assign(n, -1);
	R.assign(n, -1);
	d.assign(n, 0);
	
	rep(i, 0, n - 1) a[i] = i;
	sort(all(a), [](int x, int y) { return h[x] > h[y]; });
	for(auto i : a) {
		auto it = s.lower_bound(i);
		if(it != s.end()) {
			d[i] = d[*it] + 1;
			R[i] = *it; 	
		}
		if(it != s.begin()) {
			it = prev(it);
			L[i] = *it;
		}
		s.insert(i);
	}
//	vprint(all(L));
//	vprint(all(R));
//	vprint(all(d));
	return;
}
/*
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2 
*/
int minimum_jumps(int A, int B, int C, int D) {
	int to = C, from = -1;
	rep(i, C, D) if(h[i] > h[to]) to = i;
	rrep(i, A, B) {
		if(h[i] > h[to]) break;
		if(from == -1 || h[from] < h[i]) from = i;
	}
	if(from == -1) return -1;
	rep(i, B + 1, C - 1) if(h[i] > h[to]) return -1;
	int cnt = 0, cur = 0, id = from, ans = INF, cnt1 = 0;
	while(id != -1) {
		if(h[id] > h[to]) break;
		cur = id, cnt1 = 0; 
		while(cur < C) cur = R[cur], cnt1 ++;
		ans = min(ans, cnt + cnt1);
		cnt ++, id = L[id];
	}
	return ans;
}

Compilation message

jumps.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
jumps.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
jumps.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |                     ^~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 3032 ms 12180 KB Output is correct
4 Execution timed out 4065 ms 15212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 2 ms 200 KB Output is correct
8 Incorrect 4 ms 200 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 2 ms 200 KB Output is correct
8 Incorrect 4 ms 200 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 197 ms 12252 KB Output is correct
6 Correct 233 ms 15144 KB Output is correct
7 Correct 108 ms 7828 KB Output is correct
8 Correct 263 ms 15108 KB Output is correct
9 Correct 23 ms 2488 KB Output is correct
10 Correct 224 ms 15172 KB Output is correct
11 Correct 111 ms 15108 KB Output is correct
12 Correct 115 ms 15040 KB Output is correct
13 Correct 141 ms 15280 KB Output is correct
14 Correct 179 ms 15136 KB Output is correct
15 Execution timed out 4018 ms 15124 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 397 ms 7024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 397 ms 7024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 3032 ms 12180 KB Output is correct
4 Execution timed out 4065 ms 15212 KB Time limit exceeded
5 Halted 0 ms 0 KB -