제출 #1167362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167362		WH8	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	172 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;
		int a,b,pos;
		// above
		it=lower_bound(v.begin(),v.end(),x);
		if(it==v.end()) it=v.begin();
		a=(*it), b=(a+n)%(2*n);
		pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
		cand=min({cand, pos});
		// below
		it=upper_bound(v.begin(),v.end(),x);
		if(it==v.begin()) it=prev(v.end());
		else it=prev(it);
		a=(*it), b=(a+n)%(2*n);
		pos=min(dist(x,a)+1+dist(y,b), dist(x,b)+1+dist(y,a));
		cand=min({cand, pos});


		cout<<cand<<endl;
		
		//~ 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: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 17 / 17
• Subtask 5: 27 / 27