Submission #1227242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227242		pravcoder	Text editor (CEOI24_editor)	C++20	14 / 100	497 ms	1114112 KiB

Main

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;

#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define vec vector
#define all(x) (x).begin(), (x).end()
#define fir first
#define sec second
#define pq priority_queue

typedef long long ll;
typedef vec<int> vi;
typedef vec<vi> v2i;
typedef pair<int, int> pi;
typedef vec<pi> vpi;
typedef vec<bool> vb;
typedef vec<vec<bool>> v2b;

int n;
vi l;
pq<pair<int, pi>> q;
v2i dist;
v2b proc;
int maxd;

pi left(pi x) {
	if (x.second == 0) return {x.first-1, l[x.first-1]-1};
	return {x.first, x.second-1};
}

pi right(pi x) {
	if (x.second == l[x.first]-1) return {x.first+1, 0};
	return {x.first, x.second+1};
}

pi up(pi x) {
	return {x.first-1, min(x.second, l[x.first-1]-1)};
}

pi down(pi x) {
	return {x.first+1, min(x.second, l[x.first+1]-1)};
}


void print(v2i &dist, pi e) {
	int i = 0;
	for (auto a : dist) {
		int j = 0;
		for (auto x : a) {
			if (e.first == i && e.second == j) {
				if (x < 10) cout << " " << x << "!";
				else if (x == maxd) cout << "--!";
				else cout << x << "!";
			} else {
				if (x < 10) cout << " " << x << " ";
				else if (x == maxd) cout << "-- ";
				else cout << x << " ";
			}
			j++;
		}
		i++;
		cout << "\n";
	} cout << "\n";
}

void add(pi x, int d) {
	//cout << "adding " << x.fir << " " << x.sec << endl;
	d++;
	if (dist[x.fir][x.sec] > d) {
		dist[x.fir][x.sec] = d;
		q.push({-d, {x.fir, x.sec}});
		//cout << "added " << x.fir << " " << x.sec << " with dist=" << d << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	pi s;
	pi e;
	cin >> n;
	cin >> s.fir >> s.sec;
	cin >> e.fir >> e.sec;
	s.fir--;s.sec--;e.fir--;e.sec--;
	maxd = (s.sec + e.sec + abs(s.fir - e.fir));
	l.resize(n);
	dist.resize(n, vi());
	proc.resize(n, vb());
	rep(i, n) {
		cin >> l[i];
		l[i]++;
		dist[i].resize(l[i],maxd);
		proc[i].resize(l[i],false);
	}
	dist[s.fir][s.sec] = 0;
	
	q.push({0,s});
	while (!proc[e.fir][e.sec] && !q.empty()) {
		auto v = q.top().sec;
		q.pop();
		if (!proc[v.fir][v.sec]) {
			proc[v.fir][v.sec] = true;
			int d = dist[v.fir][v.sec];
			//cout << "processing " << v.fir << " " << v.sec << " with dist=" << d << endl;
			if (v.fir + v.sec > 0) add(left(v), d);
			if (v.fir < n-1) {
				add(right(v), d);
				add(down(v), d);
			}
			if (v.fir > 0) add(up(v), d);
			//cout << "distance array:\n";
			//print(dist, e);
		}
	}

	cout << dist[e.fir][e.sec] << endl;

	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44