神秘错误求助
查看原帖
神秘错误求助
324412
Filberte楼主2024/5/16 12:44

WA,错了10几个点。 都拍了几十万组随机数据拍不出来一个(

// LUOGU_RID: 159132849
#include <bits/stdc++.h>
#define int long long 
#define int_32 signed
using namespace std;
const int inf = 1e18;
int k, Sx, Sy, Tx, Ty;
int bSx, bSy, bTx, bTy;
int gt(int x, int y, int cx, int cy){
	int L = x * k, R = (x + 1) * k - 1;
	int U = y * k, D = (y + 1) * k - 1;
	if(L <= cx && cx <= R) return min(abs(cy - U), abs(cy - D)); 
	else return min(abs(cx - L),abs(cx - R));
} 
int dis(int x, int y){return k == 2 ? (2 * min(x, y) + 3 * abs(x - y) / 2) : (max(x, y) * 2);}
struct State{
	int x, y, ad;
}a[4], b[4];
int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
int ans;
int_32 main(){
	cin >> k >> Sx >> Sy >> Tx >> Ty;
	ans = abs(Sx - Tx) + abs(Sy - Ty);
	if(k == 1){
		cout << ans;
		return 0;
	}
	Sx += k, Sy += k, Tx += k, Ty += k;
	bSx = Sx / k, bSy = Sy / k;
	bTx = Tx / k, bTy = Ty / k;
	
	if(bSx == bTx && bSy == bTy){
		if((bSx + bSy) & 1) cout << 0;
		else cout << ans;
		return 0;
	}
	
	if((bSx + bSy) & 1) for(int i = 0;i < 4;i++) a[i] = (State){bSx, bSy, 0};
	else{
		for(int id = 0;id < 4;id++){
			int Nx = dx[id] + bSx, Ny = dy[id] + bSy;
			a[id] = (State){Nx, Ny, gt(Nx, Ny, Sx, Sy)};
		}
	}
	
	if((bTx + bTy) & 1) for(int i = 0;i < 4;i++) b[i] = (State){bTx, bTy, 0};
	else{
		for(int id = 0;id < 4;id++){
			int Nx = dx[id] + bTx, Ny = dy[id] + bTy;
			b[id] = (State){Nx, Ny, gt(Nx, Ny, Tx, Ty)};
		}
	}

	for(int i = 0;i < 4;i++) for(int j = 0;j < 4;j++) ans = min(ans, a[i].ad + b[j].ad + dis(abs(a[i].x - b[j].x), abs(a[i].y - b[j].y)));
	cout << ans;
	return 0;
}

2024/5/16 12:44
加载中...