Submission #1136211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136211		MunkhturErdenebat	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	174 ms	8620 KiB

Main

#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
#include <stdlib.h>
#define ll long long
using namespace std;
    ll a,b,c,d,e,f,m,i,j,n,h,g,l,r,ka,p,k[500000];
    map<ll,ll> maa,mii,mee;
    vector<ll> vas,vis,vii;
    pair<ll,ll> fgh;
//     double k[3005],dp[3001][3001];
int main(){
    cin>>a>>b>>ka;
    for(i=0 ; i<b ; i++){
        cin>>c;
        vas.push_back(c);
        if(c<a){
            vas.push_back(a+c);
        }
        else{
            vas.push_back(c-a);
        }
    }
    
    sort(vas.begin(),vas.end());
    vas.push_back(vas[0]+2*a);
    while(ka--){
        ll x,y;
        cin>>x>>y;
        h=abs(x-y);
        h=min(h,2*a-h);
        l=0;
        r=vas.size();
        while(l<r){
            m=(l+r-1)/2;
            if(vas[m]>x){
                r=m;
            }
            else{
                l=m+1;
            }
        }
        g=0;
        m=vas[l];
        if(m>=2*a){
            m-=2*a;
        }
        g=abs(m-x);
        g=min(g,2*a-g);
        g++;
        m=(m+a)%(2*a);
        n=abs(m-y);
        n=min(n,2*a-n);
        g+=n;
        h=min(h,g);
        if(l>0){
            l--;
        }
        else{
            l=vas.size()-2;
        }
        g=0;
        m=vas[l];
        if(m>=2*a){
            m-=2*a;
        }
        g=abs(m-x);
        g=min(g,2*a-g);
        g++;
        m=(m+a)%(2*a);
        n=abs(m-y);
        n=min(n,2*a-n);
        g+=n;
        h=min(h,g);
        if(m==x){
            
        }
        cout<<h<<endl;
        
    }
}

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