Submission #1168337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168337		mertbbm	Rainforest Jumps (APIO21_jumps)	C++20	21 / 100	21 ms	2044 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
vector<int>adj[10005];

void init(int n2, vector<int>arr){
	n=n2;
	
	vector<int>d;
	for(int x=0;x<n;x++){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()){
			adj[x].push_back(d.back());
		}
		d.push_back(x);
	}
	
	d.clear();
	for(int x=n-1;x>=0;x--){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()){
			adj[x].push_back(d.back());
		}
		d.push_back(x);
	}
}

int minimum_jumps(int a, int b, int c, int d){
	int dist[n+5];
	memset(dist,-1,sizeof(dist));
	queue<int>q;
	for(int x=a;x<=b;x++){
		dist[x]=0;
		q.push(x);
	}
	
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		for(auto it:adj[cur]){
			if(dist[it]!=-1) continue;
			dist[it]=dist[cur]+1;
			q.push(it);
		}
	}
	
	int best=1e9;
	for(int x=c;x<=d;x++){
		if(dist[x]==-1) continue;
		best=min(best,dist[x]);
	}
	
	if(best==1e9) return -1;
	else return best;
}

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