Submission #1062237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062237		PurpleCrayon	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	44 ms	9556 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 50, MOD = 1e9+7;

void solve() {
    int n, m, q; cin >> n >> m >> q;
    vector<int> v(2 * m);
    for (int i = 0; i < m; i++) {
        int x; cin >> x;
        v[i] = x;
    }
    for (int i = 0; i < m; i++) {
        v[i + m] = v[i] + n;
    }

    auto dist = [&](int x, int y) {
        ll d = abs(x - y);
        return min(d, 2 * n - d);
    };

    while (q--) {
        int x, y; cin >> x >> y;
        int i = lower_bound(v.begin(), v.end(), x) - v.begin();
        ll ans = dist(x, y);
        auto f = [&](int mid) {
            ans = min(ans, dist(x, mid) + 1 + dist((mid + n) % (2 * n), y));
        };

        f(v[i % sz(v)]);
        f(v[(i + sz(v) - 1) % sz(v)]);
        cout << ans << '\n';
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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