Submission #1228879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228879		trimkus	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	156 ms	4328 KiB

Main

#include <bits/stdc++.h>


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



int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> a(2 * M);
    for (int i = 0; i < M; ++i) {
        cin >> a[i];
        a[i + M] = a[i] + N;
    }
    sort(begin(a), end(a));
    auto calc = [&](int x, int y) -> int {
		if (x >= y) swap(x, y);
		return min(abs(y - x), abs(2 * N + x - y));
	};
	auto nxt = [&](int x) -> int {
		return (x + N) % (2 * N);
	};
    while (Q--) {
        int x, y;
        cin >> x >> y;
        int res = calc(x, y);
		{
			int l = lower_bound(begin(a), end(a), x) - begin(a);
			if (l == 0) {
				if (a[0] == x) l = x;
				else l = a.back();
			} else {
				if (l < (int)a.size()) l -= (a[l] != x);
				else l -= 1;
				l = a[l];
			}
			
			int now = calc(x, l);
			int nx = l;
			res = min(res, now + calc(nx, y));
			nx = nxt(nx);
			res = min(res, now + 1 + calc(nx, y));
		}
		{
			int r = lower_bound(begin(a), end(a), x) - begin(a);
			if (r == (int)a.size()) {
				r = a[0];
			} else {
				r = a[r];
			}
			int now = calc(x, r);
			int nx = r;
			res = min(res, now + calc(nx, y));
			nx = nxt(nx);
			res = min(res, now + 1 + calc(nx, y));
		}
		cout << res << "\n";
	}



}

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