Submission #1130063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130063		irmuun	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	55 ms	4424 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    int k[2*m];
    for(int i=0;i<m;i++){
        cin>>k[i];
    }
    for(int i=m;i<2*m;i++){
        k[i]=k[i-m]+n;
    }
    auto d=[&](int a,int b)->int{
        int r=max(a,b)-min(a,b);
        r=min(r,2*n-r);
        return r;
    };
    while(q--){
        int x,y;
        cin>>x>>y;
        int ans=max(y,x)-min(x,y);
        ans=min(ans,2*n-ans);
        int p=lower_bound(k,k+2*m,x)-k;
        p%=(2*m);
        int d1=d(x,k[p])+1+d((n+k[p])%(2*n),y);
        int d2=d(x,(n+k[p])%(2*n))+1+d(k[p],y);
        ans=min({ans,d1,d2});
        p=(p-1+2*m)%(2*m);
        d1=d(x,k[p])+1+d((n+k[p])%(2*n),y);
        d2=d(x,(n+k[p])%(2*n))+1+d(k[p],y);
        ans=min({ans,d1,d2});
        p=lower_bound(k,k+2*m,y)-k;
        p%=(2*m);
        d1=d(x,k[p])+1+d((n+k[p])%(2*n),y);
        d2=d(x,(n+k[p])%(2*n))+1+d(k[p],y);
        ans=min({ans,d1,d2});
        p=(p-1+2*m)%(2*m);
        d1=d(x,k[p])+1+d((n+k[p])%(2*n),y);
        d2=d(x,(n+k[p])%(2*n))+1+d(k[p],y);
        ans=min({ans,d1,d2});
        cout<<ans<<"\n";
    }
}

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