oj.uz

답안 #560131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
560131 2022-05-11T05:50:30 Z armashka 밀림 점프 (APIO21_jumps) C++17
4 / 100
 893 ms 15180 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin);freopen(s".out", "w", stdout);
#define nano chrono::steady_clock::now().time_since_epoch().count()
#define uid uniform_int_distribution<int>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
    
const int N = 2e5 + 10;
const int M = 2e3 + 5;
const ll inf = 1e15;
const ll mod = 998244353;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll random(ll l, ll r) { mt19937 rnd(nano); uid dist(l, r); return dist(rnd); }
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }                                   
bool even(ll n) { return (n % 2 == 0); }

int n, a[N], dis[2005][2005], d[N];
vector <int> g[N];
bool ok = 1;

void init(int N, vector <int> H) {
	n = N;
	for (int i = 1; i <= n; ++ i) {
		a[i] = H[i - 1];
		if (a[i] != i) {
			ok = 0;
		}
	}
	deque <int> d;
	a[n + 1] = 1e9;
	d.push_back(n + 1);
	for (int i = n; i >= 1; -- i) {
		while (d.sz && a[d.back()] <= a[i]) d.pop_back();
		if (d.back() != n + 1) {
			g[i].pb(d.back());
		}
		d.push_back(i);
	}
	
	if (n <= 2000) {
		for (int i = 1; i <= n; ++ i) {
			for (int j = 1; j <= n; ++ j) dis[i][j] = 1e9;
			queue <int> q;
			q.push(i);
			dis[i][i] = 0;
			while (q.sz) {
				int v = q.front();
				q.pop();
				for (auto to : g[v]) {
					if (dis[i][to] > dis[i][v] + 1) {
						dis[i][to] = dis[i][v] + 1;
						q.push(to);
					}
				}
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	int ans = 1e9;
	++ A; ++ B; ++ C; ++ D;
	if (ok) return C - B;
	if (n <= 2000) {
		for (int i = A; i <= B; ++ i) {
			for (int j = C; j <= D; ++ j) {
				ans = min(ans, dis[i][j]);
			}
		}
	} else {
		queue <ll> q;
		for (int i = 1; i <= n; ++ i) d[i] = 1e9;
		for (int i = A; i <= B; ++ i) q.push(i), d[i] = 0;
		while (q.sz) {
			int v = q.front();
			q.pop();
			for (auto to : g[v]) {
				if (d[to] > d[v] + 1) {
					d[to] = d[v] + 1;
					q.push(to);
				}
			}
		}
		for (int i = C; i <= D; ++ i) ans = min(ans, d[i]);
	}
	return (ans == 1e9 ? -1 : ans);
}

//signed main() {
//	init(7, {3, 2, 1, 6, 4, 5, 7});
//	cout << minimum_jumps(0, 1, 2, 2);
//}

Compilation message

jumps.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 120 ms 12420 KB Output is correct
4 Correct 893 ms 14360 KB Output is correct
5 Correct 838 ms 9748 KB Output is correct
6 Correct 802 ms 14368 KB Output is correct
7 Correct 673 ms 11396 KB Output is correct
8 Correct 813 ms 14336 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 31 ms 12532 KB Output is correct
6 Correct 45 ms 14184 KB Output is correct
7 Correct 23 ms 9324 KB Output is correct
8 Correct 42 ms 15180 KB Output is correct
9 Correct 8 ms 6416 KB Output is correct
10 Correct 37 ms 14080 KB Output is correct
11 Correct 35 ms 14372 KB Output is correct
12 Correct 57 ms 14472 KB Output is correct
13 Incorrect 55 ms 14160 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 120 ms 12420 KB Output is correct
4 Correct 893 ms 14360 KB Output is correct
5 Correct 838 ms 9748 KB Output is correct
6 Correct 802 ms 14368 KB Output is correct
7 Correct 673 ms 11396 KB Output is correct
8 Correct 813 ms 14336 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 4 ms 4944 KB Output is correct
11 Correct 4 ms 4944 KB Output is correct
12 Correct 4 ms 4944 KB Output is correct
13 Correct 4 ms 5072 KB Output is correct
14 Incorrect 6 ms 5968 KB Output isn't correct
15 Halted 0 ms 0 KB -