求助ABC F
  • 板块学术版
  • 楼主assert_0
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/11 22:18
  • 上次更新2024/5/12 09:49:38
查看原帖
求助ABC F
532536
assert_0楼主2024/5/11 22:18
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 210000
/*
    1 

4       2

    3 
*/
int k,nx,ny,ex,ey;
int t(int x,int y){
	if(x>=0){
		return x/y;
	}
	else{
		if((-x)%y==0){
			return -(-x)/y;
		}
		else{
			return -(-x)/y-1;
		}
	}
}
int s1(int x,int y){
	return t(y,k)*k+k-y;
}
int s2(int x,int y){
	return t(x,k)*k+k-x;
}
int s3(int x,int y){
	return k+1-s1(x,y);
}
int s4(int x,int y){
	return k+1-s2(x,y);
}
pair<int,int> p(int x,int y){
	return make_pair(t(x,k),t(y,k));
}
pair<int,int> p1(int x,int y){
	return make_pair(t(x,k),t(y,k)+1);
}
pair<int,int> p2(int x,int y){
	return make_pair(t(x,k)+1,t(y,k));
}
pair<int,int> p3(int x,int y){
	return make_pair(t(x,k),t(y,k)-1);
}
pair<int,int> p4(int x,int y){
	return make_pair(t(x,k)-1,t(y,k));
}
int check(int x,int y){
	return (t(x,k)+t(y,k))%2==1;
}
int dis(pair<int,int> a,pair<int,int> b){
	if(k==1){
		return abs(a.first-b.first)+abs(a.second-b.second);
	}
	if(k==2){
		return 2*min(abs(a.first-b.first),abs(a.second-b.second))+3*abs(abs(a.first-b.first)-abs(a.second-b.second))/2;
	}
	return 2*max(abs(a.first-b.first),abs(a.second-b.second));
}
signed main(){
	int ans=1e18;
	cin>>k>>nx>>ny>>ex>>ey;
	if((t(nx,k)+t(ny,k)==t(nx,k)+t(ny,k))&&(!check(nx,ny))&&(!check(ex,ey))&&(abs(nx-ny)<=k-1)&&(abs(ex-ey)<=k-1)){
		ans=abs(nx-ex)+abs(ny-ey);
	}
	if(check(nx,ny)&&check(ex,ey)){
		ans=min(ans,dis(p(nx,ny),p(ex,ey)));
	}
	else if(check(nx,ny)){
		int minn=min(min(dis(p(nx,ny),p1(ex,ey))+s1(ex,ey),dis(p(nx,ny),p2(ex,ey))+s2(ex,ey)),min(dis(p(nx,ny),p3(ex,ey))+s3(ex,ey),dis(p(nx,ny),p4(ex,ey))+s4(ex,ey)));
		ans=min(ans,minn);
	}
	else if(check(ex,ey)){
		swap(nx,ex);
		swap(ny,ey);
		int minn=min(min(dis(p(nx,ny),p1(ex,ey))+s1(ex,ey),dis(p(nx,ny),p2(ex,ey))+s2(ex,ey)),min(dis(p(nx,ny),p3(ex,ey))+s3(ex,ey),dis(p(nx,ny),p4(ex,ey))+s4(ex,ey)));
		ans=min(ans,minn);
	}
	else{
		int minn1=min(min(dis(p1(nx,ny),p1(ex,ey))+s1(nx,ny)+s1(ex,ey),dis(p1(nx,ny),p2(ex,ey))+s1(nx,ny)+s2(ex,ey)),min(dis(p1(nx,ny),p3(ex,ey))+s1(nx,ny)+s3(ex,ey),dis(p1(nx,ny),p4(ex,ey))+s1(nx,ny)+s4(ex,ey)));
		int minn2=min(min(dis(p2(nx,ny),p1(ex,ey))+s2(nx,ny)+s1(ex,ey),dis(p2(nx,ny),p2(ex,ey))+s2(nx,ny)+s2(ex,ey)),min(dis(p2(nx,ny),p3(ex,ey))+s2(nx,ny)+s3(ex,ey),dis(p2(nx,ny),p4(ex,ey))+s2(nx,ny)+s4(ex,ey)));
		int minn3=min(min(dis(p3(nx,ny),p1(ex,ey))+s3(nx,ny)+s1(ex,ey),dis(p3(nx,ny),p2(ex,ey))+s3(nx,ny)+s2(ex,ey)),min(dis(p3(nx,ny),p3(ex,ey))+s3(nx,ny)+s3(ex,ey),dis(p3(nx,ny),p4(ex,ey))+s3(nx,ny)+s4(ex,ey)));
		int minn4=min(min(dis(p4(nx,ny),p1(ex,ey))+s4(nx,ny)+s1(ex,ey),dis(p4(nx,ny),p2(ex,ey))+s4(nx,ny)+s2(ex,ey)),min(dis(p4(nx,ny),p3(ex,ey))+s4(nx,ny)+s3(ex,ey),dis(p4(nx,ny),p4(ex,ey))+s4(nx,ny)+s4(ex,ey)));
		ans=min(ans,min(min(minn1,minn2),min(minn3,minn4)));
	}
	cout<<ans<<endl;
	return 0;
}

WA*4,蒟蒻调不出来/kk

2024/5/11 22:18
加载中...