Submission #1060622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060622		Szymon_Pilipczuk	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	162 ms	9556 KiB

Main

#include <iostream>
using namespace std;
int n;
int distance(int a,int b)
{
    int c;
    if(a<b)
    {
        c = a;
        a = b;
        b = c;
    }
    return min(a-b,b+2*n-a);

}
int main()
{
    int m,q;
    cin>>n>>m>>q;
    int fr[2*m];
    int a;
    for(int i = 0;i<m;i++)
    {

        cin>>a;
        a-=1;
        fr[i] = a;
        fr[i+m] = a+n;
    }
    int x,y;
    for(int i = 0;i<q;i++)
    {
        cin>>x>>y;
        x--;
        y--;
        int lx,rx;
        if(x<fr[0] || x>fr[2*m-1])
        {
            lx = 2*m-1;
            rx = 0;
        }
        else
        {
            lx = 0;
            rx = 2*m-1;
            int mid;
            while(lx+1<rx)
            {
                mid = (lx+rx)/2;
                if(fr[mid]>x)
                {
                    rx = mid;
                }
                else
                {
                    lx = mid;
                }
            }


        }
        int d =0;
        int dl = 0;
        int dr = 0;
        d = distance(x,y);
        dl = distance(x,fr[lx])+1+distance((fr[lx]+n)%(2*n),y);
        dr = distance(x,fr[rx])+1+distance((fr[rx]+n)%(2*n),y);
        int ans = min(d,min(dl,dr));
        cout<< ans<<"\n";




    }
}

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