Submission #1168240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168240		SheepHeads	Circle Passing (EGOI24_circlepassing)	C++20	31 / 100	2096 ms	8276 KiB

Main

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

int n, m, q;
const int INF = 1e9+7;
vector<int> bridge;

int getDist(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> getIdx(int x){
    if(x < bridge.at(0) || x > bridge.at(2*m-1)){
        return {0, 2*m-1};
    }else if(x == bridge.at(0)){
        return {0, 0};
    }else if(x == bridge.at(2*m-1)){
        return {2*m-1, 2*m-1};
    }

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

    while(l < r){
        int mid = (l + ((r-l)>>1));

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

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

    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.at(i);
        bridge.at(i+m) = bridge.at(i)+n;
    }
    
    // for(auto itr : bridge){
    //     cout << itr << "\n";
    // }

    while(q--){
        int x, y;
        cin>>x>>y;

        pair<int, int> b = getIdx(x);
        int brute = getDist(x, y);
        int f = getDist(x, bridge.at(b.first)) + getDist(y, bridge.at((b.first+m)%(2*m)))+1;
        int s = getDist(x, bridge.at(b.second)) + getDist(y, bridge.at((b.second+m)%(2*m)))+1;

        // cout << brute << " " << f << " " << s << "\n";

        cout << min(brute, min(f, s)) << "\n";
    }

    return 0;
}

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