Submission #1166112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166112		rotated	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	387 ms	47512 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int dist(int s, int e) {
    return min(abs(s - e), 2*n - abs(s - e));
}
int32_t main() {
    int m, q; cin >> n >> m >> q;
    set<int> s;
    for (int i = 0; i < m; i++) {
        int x; cin >> x;
        s.insert(x);
        s.insert(x + n);
    }
    int x, y;
    for (int i = 0; i < q; i++) {
        cin >> x >> y;
        if ((y - x + 2*n) % (2*n) < n) swap(x,y);
        //now x to y is the longer arc
        
        int ans = dist(x, y);
        set<int>::iterator d = s.lower_bound(x);
        if (d == s.end()) d = s.begin();
        int d1 = *d;
        int d2 = (d1 + n) % (2*n);
        ans = min(ans, dist(x, d1) + dist(d2, y) + 1);
        
        d = s.upper_bound(y);
        if (d == s.begin()) d = s.end();
        d--;
        d1 = *d;
        d2 = (d1 + n) % (2*n);
        ans = min(ans, dist(y, d1) + dist(d2, x) + 1);
        cout << ans << "\n";
    }
}

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