Submission #1137659

#TimeUsernameProblemLanguageResultExecution timeMemory
1137659Jawad_Akbar_JJText editor (CEOI24_editor)C++20
19 / 100
134 ms39556 KiB
#include <iostream>
#include <queue>

using namespace std;
const int N = 1e6 + 10;
int l[N];
int n, a, b, c, d;

void solve1(){
	if (a == c and b == d){
		cout<<0<<'\n';
		exit(0);
	}

	if (a == 1 and c == 1){
		int Ans = abs(d - b);
		if (b < d) Ans = min(Ans, 2 + l[1] + 1 - d);
		else Ans = min(Ans, 1 + d);
		cout<<Ans<<'\n';
	}
	else if (c == 2)
		cout<<1<<'\n';
	else
		cout<<min(d, l[1] + 1 - d + 1)<<'\n';
	exit(0);
}

int Mn[1005][5005], seen[1005][5005];
queue<pair<int,int>> Q;

void update(int i, int j, int c){
	if (i < 1 or i > n or j > l[i] + 1 or seen[i][j]) return;
	seen[i][j] = 1;
	Mn[i][j] = c;
	Q.push({i, j});
}

void bfs(){
	Q.push({a, b});
	seen[a][b] = 1;

	while (Q.size() > 0){
		auto [i, j] = Q.front();
		Q.pop();

		update(i - 1, min(j, l[i-1] + 1), Mn[i][j] + 1);
		update(i + 1, min(j, l[i+1] + 1), Mn[i][j] + 1);

		if (j == l[i] + 1) update(i + 1, 1, Mn[i][j] + 1);
		else update(i, j + 1, Mn[i][j] + 1);

		if (j == 1) update(i - 1, l[i-1] + 1, Mn[i][j] + 1);
		else update(i, j - 1, Mn[i][j] + 1);
	}
	cout<<Mn[c][d]<<'\n';
	exit(0);
}

int main(){
	cin>>n>>a>>b>>c>>d;

	for (int i=1;i<=n;i++)
		cin>>l[i];

	if (n <= 2) solve1();

	bfs();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...