Submission #1044452

#TimeUsernameProblemLanguageResultExecution timeMemory
1044452alex_2008Text editor (CEOI24_editor)C++14
14 / 100
69 ms139492 KiB
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int l[N];
int dist[1050][5050];
vector <vector<int>> G;
queue <pair<int, int>> Q;
void check(pair<int, int> esim, pair <int, int> par) {
	int d = dist[par.first][par.second];
	int x = esim.first;
	int y = esim.second;
	if (!dist[x][y]) {
		dist[x][y] = d + 1;
		Q.push({ x, y });
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	int sl, sc, el, ec;
	cin >> sl >> sc >> el >> ec;
	int sm = 0;
	for (int i = 1; i <= n; i++) {
		cin >> l[i];
		sm += (l[i] + 1);
	}
	G.resize(sm + 1);
	dist[sl][sc] = 1;
	Q.push({ sl, sc });
	while (!Q.empty()) {
		pair <int, int> k = Q.front(); Q.pop();
		//cout << k.first << " " << k.second << "\n";
		pair <int, int> cur = k;
		if (k.second == 1) {
			if (k.first != 1) {
				cur.first--;
				cur.second = l[cur.first] + 1;
			}
		}
		else cur.second--;
		check(cur, k);
		cur = k;
		if (k.second == l[k.first] + 1) {
			if (k.first != n) {
				cur.first++;
				cur.second = 1;
			}
		}
		else cur.second++;
		check(cur, k);
		cur = k;
		if (cur.first != 1) {
			cur.first--;
			cur.second = min(l[cur.first] + 1, cur.second);
		}
		check(cur, k);
		cur = k;
		if (cur.first != n) {
			cur.first++;
			cur.second = min(l[cur.first] + 1, cur.second);
		}
		check(cur, k);
	}
	cout << dist[el][ec] - 1 << "\n";
}
#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...