Submission #1167356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167356		WH8	Circle Passing (EGOI24_circlepassing)	C++20	14 / 100	134 ms	8684 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)

#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
int n;
int dist(int a, int b){
	return min(abs(a-b), 2*n-abs(a-b));
}

signed main(){
	int m,q;cin>>n>>m>>q;
	vector<int> v;
	for(int i=0;i<m;i++){
		int c;cin>>c;
		v.pb(c);
		v.pb(c+n);
	}
	sort(v.begin(),v.end());
	for(int i=0;i<q;i++){
		int x,y;cin>>x>>y;
		if(x<y)swap(x,y);
		int cand=dist(x,y);
		//~ printf("straight is %lld\n", cand);
		//~ int xp=(x+(n+1)/2+(n%2==0?1:0))%(2*n), xm=(x-(n+1)/2+(n%2==0?-1:0) + 2*n)%(2*n);
		int yp=(y+(n/2)+(n%2==0?-1:0))%(2*n), ym=(y-(n/2)+(n%2==0?1:0) + 2*n)%(2*n);
		vector<int>::iterator it;
		//~ printf("bounds are ym %lld to yp %lld \n", ym, yp);
		if(yp<ym){
			it=lower_bound(v.begin(),v.end(),ym);
			if(it!=v.end()){
				int a=(*it), b=(a+n)%(2*n);
				int pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
				cand=min({cand, pos});
			}
			it=upper_bound(v.begin(),v.end(),yp);
			if(it!=v.begin()){
				int a=(*prev(it)), b=(a+n)%(2*n);
				int pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
				cand=min({cand, pos});
			}
			it=v.begin();
			if(it!=v.end() and (*it)<=yp){
				int a=(*it), b=(a+n)%(2*n);
				int pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
				cand=min({cand, pos});
			}
			it=prev(v.end());
			if(it!=v.begin() and (*prev(it))>=ym){
				int a=(*prev(it)), b=(a+n)%(2*n);
				int pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
				cand=min({cand, pos});
			}
		}
		else{
			it=lower_bound(v.begin(),v.end(),ym);
			if(it!=v.end() and (*it)<=yp){
				int a=(*it), b=(a+n)%(2*n);
				//~ printf("one way is %lld, other way is %lld\n", dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,b));
				int pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
				cand=min({cand, pos});

				//~ printf("a is %lld, b is %lld, pos is %lld \n", a, b,pos);
			}
			it=upper_bound(v.begin(),v.end(),yp);
			if(it!=v.begin() and (*prev(it))>=ym){
				int a=(*prev(it)), b=(a+n)%(2*n);
				int pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
				cand=min({cand, pos});
			}
		}
		cout<<cand<<endl;
		//~ int lb=xp, ub=yp;
		//~ if(dist(xm,ym)<dist(xp,yp)){
			//~ lb=xm,ub=ym;
		//~ }
		//~ printf("bounds are %lld to %lld\n", lb, ub);
		//~ int a=-1, b=-1;
		//~ if(lb>ub){
			
		//~ }
		//~ else{
			
		//~ }
		//~ auto it=lower_bound(v.begin(),v.end(),xp);
		//~ if(it!=v.end() and (*it)<=yp){
			//~ int a=(*it), b=((*it)+n)%(2*n);
			//~ int cand=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,b));
			//~ printf("cand is %lld\n", cand);
			//~ ans=min(ans,cand);
		//~ }
		//~ cout<<ans<<endl;
	}
}

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