Submission #1166028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166028		Pwo	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	49 ms	8624 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, q;
vector<int> v;

int d(int x, int y) {
	return min(abs(y - x), min(2 * n + x - y, 2 * n - x + y));
}

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int x; cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < m; i++)
		v.push_back(v[i] + n);
	
	while (q--) {
		int x, y; cin >> x >> y;
		int ans = d(x, y);
		int val = (x > v.back() ? v[0] : *lower_bound(v.begin(), v.end(), x));
		ans = min(ans, d(x, val) + d((val + n) % (2 * n), y) + 1);
		val = (v[0] > x ? v.back() : *--upper_bound(v.begin(), v.end(), x));
		ans = min(ans, d(x, val) + d((val + n) % (2 * n), y) + 1);
		cout << ans << '\n';
	}
}

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