Submission #1058700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058700		Szymon_Pilipczuk	Circle Passing (EGOI24_circlepassing)	C++17	0 / 100	112 ms	4236 KiB

Main

#include <iostream>
#include <vector>
using namespace std;
vector<int> bf;
int n,m;
int bin_search(int c)
{
    int l = 0;
    int r = m-1;
    int mid;
    while(r>l+1)
    {
        mid = (r+l)/2;
        if(bf[mid]>c)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    return l;
}
int main()
{
    int q;
    cin>>n>>m>>q;
    int cu;
    for(int i = 0;i<m;i++)
    {
        cin>>cu;
        bf.push_back(cu);
    }
    int x,y;

    for(int i = 0;i<q;i++)
    {
        cin>>x>>y;
        if(x<y)
        {
            cu = y;
            y= x;
            x = cu;
        }
        int ans = min(x-y,y-x+2*n);
        if(x>=n && y>=n)
        {
            x-=n;
            y-=n;
        }
        int f = bin_search(y);
        int s = f+1;
        if(s == m)
        {
            s = 0;
        }
        if(bf[f]>y)
        {
            f =m-1;
        }
        ans = min(ans,1+max(y-bf[f],bf[f]-y)+max(x-(bf[f]+n),(bf[f]+n)-x));
        ans = min(ans,1+max(y-bf[s],bf[s]-y)+max(x-(bf[s]+n),(bf[s]+n)-x));
        cout<<ans<<"\n";


    }



}

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