Submission #1120820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120820		ezzzay	Circle Passing (EGOI24_circlepassing)	C++14	100 / 100	272 ms	14028 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
vector<int>ans;
int n,m,q;

vector<int>v={-1,INT_MAX};
int fun(int x, int y){
    int h=abs(y-x);
    return min(h,2*n-h);
}
int find(int a, int b){

    auto it=lower_bound(v.begin(),v.end(),a);
    int x=*it;
    it--;
    int y= *it;
    int p=fun(a,b);
    if(x!=INT_MAX){
        int z;
        if(x<n)z=n+x;
        else z=x-n;
        p=min(p,fun(a,x)+fun(b,z)+1);
    }
    
    if(y!=-1){
        int z;
        if(y<n)z=n+y;
        else z=y-n;
        p=min(p,fun(a,y)+fun(b,z)+1);
    }
    return p;
        
}
signed main(){
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int a;
        cin>>a;
        v.pb(a);
        v.pb(a+n);
    }
    sort(v.begin(),v.end());
    while(q--){
        int a,b;
        cin>>a>>b;
        int p=min(find(b,a),find(a,b));
        ans.pb(p);
    }
    for(auto a:ans)cout<<a<<endl;
}

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