Submission #1192949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192949		nguyenkhangninh99	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	38 ms	8272 KiB

Main

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

#define int long long

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

int dist(int x, int y){
    if(x < n) return min(abs(y - x), x + 2 * n - y);
    else return min(abs(y - x), 2 * n - x + y);
}

pair<int, int> get(int x){
    if(x < bridge[0] || x > bridge[2 * m - 1]) return {0, 2 * m - 1};
    else if(x == bridge[0]) return {0, 0};
    else if(x == bridge[2 * m - 1]) return {2 * m - 1, 2 * m - 1};

    int l = 0, r = 2 * m - 1;

    while(l < r){
        int mid = (r + l) / 2;

        if(bridge[mid] > x) r = mid;
        else if(bridge[mid] < x) l = mid;
        else if(bridge[mid] == x) return {mid, mid};

        if(r - l < 2) return {l, r};
    }

    return {min(r, l), max(r, l)};
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> q;
    bridge = vector<int>(2 * m);

    for(int i = 0; i < m; i++){
        cin >> bridge[i];
        bridge[i + m] = bridge[i] + n;
    }
    
    while(q--){
        int x, y; cin >> x >> y;

        pair<int, int> b = get(x);
        int f = dist(x, bridge[b.first]) + dist(y, bridge[(b.first + m) % (2 * m)]) + 1;
        int s = dist(x, bridge[b.second]) + dist(y, bridge[(b.second + m) % (2 * m)]) + 1;

        cout << min(dist(x, y), min(f, s)) << "\n";
    }
}

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