Submission #1109848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109848		Raj	Circle Passing (EGOI24_circlepassing)	C++11	100 / 100	433 ms	52560 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n,M,Q;
set <int> s;
int dist(int x,int y)
{
    return min(abs(x-y),n*2-abs(x-y));
}
int shc(int x, int y)
{
    auto it=s.lower_bound(x);
    if(it==s.end())
        it=s.begin();
    int val=*it;
    if(val>n)
        val-=n;
    else
        val+=n;
    int ans=min(dist(x,y),dist(x,*it)+1+dist(val,y));
    if(it==s.begin())
        it=prev(s.end());
    else
        it=prev(it);
    val=*it;
    if(val>n)
        val-=n;
    else
        val+=n;
    ans=min(ans,dist(x,*it)+1+dist(val,y));
    return ans;
}
int main()
{
    cin>>n>>M>>Q;
    for(int i=1;i<=M;++i)
    {
        int x;
        cin>>x;
        if(x>n)
            s.insert(2*n-x);
        else
            s.insert(x+n);
        s.insert(abs(x));
    }
    for(int i=1;i<=Q;++i)
    {
        int a,b;
        cin>>a>>b;
        cout<<shc(a,b)<<'\n';
    }
    return 0;
}

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