Submission #1147658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147658		samia	Circle Passing (EGOI24_circlepassing)	C++20	31 / 100	811 ms	133592 KiB

Main

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
using ll = long long ;
ll ri,ro;
vector<ll>v;
ll n,m,q;
ll bs(ll x){
    ll l,r;
    l=0;
    r=v.size()-1;
    ll c=0;
    if(x>v[r] or x<v[l]){ri=l; ro=r;}
    else{
    while(true){
        ri=l; ro=r;
         c=(l+r+1)/2;
        if(x>v[c]){ l=c+1; }
      if(x<v[c]){r=c-1;}
      if(r==l){  ri=l; ro=r; break;}
     if(x==v[c] or r<l){ break;}
    }
    }

return 0;
}


int main() {
 

cin>>n>>m>>q;
ll bestie=0;
ll b;
map<ll,ll>p;
map<ll,ll>s;



for(ll so=0;so<m;so++){
    cin>>bestie;
    b=(bestie+n)%(2*n);
 
        v.push_back(bestie);
       //  v.push_back(bestie+(2*n));
        v.push_back(b);
         //  v.push_back(b+(2*n));
  p[bestie]=b;
   p[b]=bestie;
s[bestie]=1;
    s[b]=1;
}

sort(v.begin(),v.end());


    ll x,y;
    ll ans=0;
    while(q--){
        cin>>x>>y;
       ans=min(abs(x-y),(2*n)-abs(x-y)); 
      bs(x);
       // cout<<v[ri]<<" "<<v[ro]<<" "<<endl;
      // bs(x+2*n);
       
     
          
ans=min(ans,min((2*n)-abs(x-v[ro]),abs(x-v[ro]))+1+min((2*n)-abs(y-p[v[ro]]),abs(y-p[v[ro]])));
  ans=min(ans,min((2*n)-abs(x-v[ri]),abs(x-v[ri]))+1+min((2*n)-abs(y-p[v[ri]]),abs(y-p[v[ri]])));
      
      cout<<ans<<endl;
    }






}

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