Submission #1229285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229285		ripolas	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	169 ms	4644 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n;
int circleDistance (int x, int y){
    if(x>y)swap(x,y); // 5 7
    return min(y-x,x+n-y);
}
int main(){
    int m,q;
    cin>>n>>m>>q;
    n*=2;
    vector<int> k;
    for(int i = 0;i<m;i++){
        int a;
        cin>>a;
        k.push_back(a);
        k.push_back((a+n/2)%n);
    }
    sort(k.begin(),k.end());
    for(int i = 0;i<q;i++){
        int x,y;
        cin>>x>>y;
        int rez = circleDistance(x,y);
        auto it = lower_bound(k.begin(),k.end(),x);
        int a,b;
        if(it!=k.end()){
            auto it2 = k.end()-1;
            if(it!=k.begin()){
                it2 = it-1;
            }
            a = *it;
            b = *it2;
        }else{
            a = k[k.size()-1];
            b = k[0];
        }
        int pathA = circleDistance(x,a)+1+circleDistance(y,(a+n/2)%n);
        int pathB = circleDistance(x,b)+1+circleDistance(y,(b+n/2)%n);
        cout<<min({rez,pathA,pathB})<<endl;
    }
}
/*
4 2 1
1 2
5 4
*/

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