Submission #1168393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168393		SheepHeads	Circle Passing (EGOI24_circlepassing)	C++20	31 / 100	2095 ms	8264 KiB

Main

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

int n, m, q;
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 = (r+l)/2;
        // cout << l << " " << r << " " << mid << endl;

        if(bridge.at(mid) > x){
            r = mid;
            // cout << "HERE1\n";
        }else if(bridge.at(mid) < x){
            l = mid;
            // cout << "HERE2\n";
        }else if(bridge.at(mid) == x){
            return {mid, mid};
            // cout << "HERE3\n";
        }
    }

    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;

        int brute = getDist(x, y);

        pair<int, int> b = getIdx(x);
        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