Submission #1109843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109843		Raj	Circle Passing (EGOI24_circlepassing)	C++11	0 / 100	2072 ms	36656 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)
{
    int vst,vdr;
    if(upper_bound(s.begin(),s.end(),x)==s.end())
        vdr=*s.begin();
    else
        vdr=*upper_bound(s.begin(),s.end(),x);
    
    if(lower_bound(s.begin(),s.end(),x)!=s.end())
    {
        if(*lower_bound(s.begin(),s.end(),x)==x)
            vst=x;
        else
        {   
            if(lower_bound(s.begin(),s.end(),x)==s.begin())
                vst=*s.rbegin();
            else
                vst=*--upper_bound(s.begin(),s.end(),x);
        }
    }
    else
    {
        auto it=lower_bound(s.begin(),s.end(),x);
        --it;
        vst=*lower_bound(s.begin(),s.end(),x);
    }
    int prst,prdr;
    if(vst>4)
        prst=vst-n;
    else
        prst=vst+n;
    if(vdr>4)
        prdr=vdr-n;
    else
        prdr=vdr+n;    
    int d1=dist(x,y);
    int d2=dist(x,vst)+1+dist(prst,y);
    int d3=dist(x,vdr)+1+dist(prdr,y);
    return min(d1,min(d2,d3));
}
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: 0 / 14
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 27