Submission #1048639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048639		EntityPlantt	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	144 ms	24104 KiB

Main

#include <iostream>
#include <set>
using namespace std;

int n;
set <int> k;
inline const int fastest(const int &x, const int &y) {
	return min(abs(x - y), 2 * n - abs(x - y));
}
inline void calc(int &ans, int &x, int &y, const int &z) {
	ans = min(ans, min(fastest(x, z) + fastest(z + n, y), fastest(y, z) + fastest(z + n, x)) + 1);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int m, q;
	cin >> n >> m >> q;
	while (m--) {
		int x;
		cin >> x;
		k.insert(x);
	}
	while (q--) {
		int x, y, ans;
		cin >> x >> y;
		ans = fastest(x, y);
		if (y < x) swap(x, y);
		if (x >= n) {
			x -= n;
			y = (y + n) % (n << 1);
		}
		set<int>::iterator z = k.lower_bound(x), w = k.lower_bound(y % n);
		if (z == k.end()) z = k.begin();
		if (w == k.end()) w = k.begin();
		calc(ans, x, y, *z);
		calc(ans, x, y, *w);
		if (z == k.begin()) z = k.end();
		if (w == k.begin()) w = k.end();
		z--; w--;
		calc(ans, x, y, *z);
		calc(ans, x, y, *w);
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 17 / 17
• Subtask 5: 27 / 27