제출 #1342752

#제출 시각아이디문제언어결과실행 시간메모리
1342752vjudge1Text editor (CEOI24_editor)C++20
14 / 100
2524 ms1114112 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl '\n'
#define Valerian void
#define Valerian_or_Habil ios::sync_with_stdio(false); cin.tie(0);

using namespace std;

ll encode(int r, int c) {
	return (1LL * r << 32) | c;
}

Valerian solve() {
	int n;
	cin >> n;
	int sl, sc, el, ec;
	cin >> sl >> sc >> el >> ec;

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

	if (sl == el && sc == ec) {
		cout << 0 << endl;
		return;
	}

	unordered_map<ll, int> dist;
	queue<pair<int,int>> q;

	q.push({sl, sc});
	dist[encode(sl, sc)] = 0;

	while (!q.empty()) {
		pair<int,int> cur = q.front();
		q.pop();
		int r = cur.first;
		int c = cur.second;

		int d = dist[encode(r, c)];

		if (r == el && c == ec) {
			cout << d << endl;
			return;
		}

		vector<pair<int,int>> moves;

		if (c > 1) {
			moves.pb({r, c - 1});
		}
		else if (r > 1) {
			moves.pb({r - 1, l[r - 1] + 1});
		}

		if (c < l[r] + 1) {
			moves.pb({r, c + 1});
		}
		else if (r < n) {
			moves.pb({r + 1, 1});
		}

		if (r > 1) {
			moves.pb({r - 1, min(c, l[r - 1] + 1)});
		}
		if (r < n) {
			moves.pb({r + 1, min(c, l[r + 1] + 1)});
		}

		for (auto &m : moves) {
			int nr = m.first;
			int nc = m.second;

			ll key = encode(nr, nc);
			if (!dist.count(key)) {
				dist[key] = d + 1;
				q.push({nr, nc});
			}
		}
	}
}

int main() {
	Valerian_or_Habil;
	solve();
}
#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...