Submission #1207556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207556		trimkus	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	170 ms	4624 KiB

Main

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



int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> tel;
	for (int i = 0; i < m; ++i) {
		int a;
		cin >> a;
		tel.push_back(a);
		tel.push_back(a + n);
	}
	sort(begin(tel), end(tel));
	//~ vector<int> l(2 * n), r(2 * n);
	//~ for (int i = 0, j = 0; i < 2 * n; ++i) {
		//~ while (j + 1 < (int)tel.size() && tel[j + 1] <= i) j++;
		//~ l[i] = (tel[j] > i ? tel.back() : tel[j]);
	//~ }
	//~ for (int i = 2 * n - 1, j = tel.size() - 1; i >= 0; --i) {
		//~ while (j - 1 >= 0 && tel[j - 1] >= i) j--;
		//~ r[i] = (tel[j] < i ? tel[0] : tel[j]);
	//~ }
	//~ for (int i = 0; i < 2 * n; ++i) {
		//~ cout << l[i] << " " << r[i] << "\n";
	//~ }
	auto calc = [&](int x, int y) -> int {
		//~ cout << x << " " << y << " -> ";
		if (x >= y) swap(x, y);
		//~ cout << x << " " << y << " dist = " << min(abs(y - x), abs(2 * n + x - y)) << endl;
		return min(abs(y - x), abs(2 * n + x - y));
	};
	auto nxt = [&](int x) -> int {
		return (x + n) % (2 * n);
	};
	while (q--) {
		int a, b;
		cin >> a >> b;
		int res = calc(a, b);
		//~ cout << res << " -> ";
		{
			int l = lower_bound(begin(tel), end(tel), a) - begin(tel);
			if (l == 0) {
				if (tel[0] == a) l = a;
				else l = tel.back();
			} else {
				if (l < (int)tel.size()) l -= (tel[l] != a);
				else l -= 1;
				l = tel[l];
			}
			
			int now = calc(a, l);
			int na = l;
			res = min(res, now + calc(na, b));
			//~ cout << res << "= res \n";
			//~ cout << na << " -> ";
			na = nxt(na);
			//~ cout << na << endl;
			//~ cout << now << " = " << na << " = " << calc(na, b) << endl;
			res = min(res, now + 1 + calc(na, b));
		}
		{
			int r = lower_bound(begin(tel), end(tel), a) - begin(tel);
			if (r == (int)tel.size()) {
				r = tel[0];
			} else {
				r = tel[r];
			}
			int now = calc(a, r);
			int na = r;
			res = min(res, now + calc(na, b));
			na = nxt(na);
			res = min(res, now + 1 + calc(na, b));
		}
		cout << res << "\n";
	}
}

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