Submission #33033

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include"porter.h"

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll INF=1LL<<61;

template<class T>
class gint{
public:
	T a,b; // a+bi
	gint(const T &a=0,const T &b=0):a(a),b(b){}

	gint &operator+=(const gint &z){ a+=z.a; b+=z.b; return *this; }
	gint &operator-=(const gint &z){ a-=z.a; b-=z.b; return *this; }
	gint &operator*=(const gint &z){
		gint w=*this;
		a=w.a*z.a-w.b*z.b;
		b=w.a*z.b+w.b*z.a;
		return *this;
	}
	gint &operator/=(const gint &z){ // 割り切れないときは、実部・虚部とも最も近い整数に丸める
		gint w=*this;
		T de=z.a*z.a+z.b*z.b,nu;
		bool sgn;
		nu=w.a*z.a+w.b*z.b; sgn=(nu>=0); if(!sgn) nu*=-1; a=nu/de+(nu%de<=de/2?0:1); if(!sgn) a*=-1;
		nu=w.b*z.a-w.a*z.b; sgn=(nu>=0); if(!sgn) nu*=-1; b=nu/de+(nu%de<=de/2?0:1); if(!sgn) b*=-1;
		return *this;
	}
	gint &operator%=(const gint &z){ return *this-=*this/z*z; }

	gint operator+(const gint &z)const{ return gint(*this)+=z; }
	gint operator-(const gint &z)const{ return gint(*this)-=z; }
	gint operator*(const gint &z)const{ return gint(*this)*=z; }
	gint operator/(const gint &z)const{ return gint(*this)/=z; }
	gint operator%(const gint &z)const{ return gint(*this)%=z; }

	gint operator-()const{ return gint(-a,-b); }

	bool operator==(const gint &z)const{ return a==z.a && b==z.b; }
	bool operator!=(const gint &z)const{ return a!=z.a || b!=z.b; }
};

template<class T>
T xgcd(T a,T b,T &x,T &y){
	if(b==0){ x=1; y=0; return a; }
	T g=xgcd(b,a%b,y,x); y-=a/b*x;
	return g;
}

int E,S;
gint<ll> P; // 現在位置

void init(int E,int S){
	::E=E;
	::S=S;
	P.a=P.b=0;
}

int moveTo(int tx,int ty,int A,int B){
	int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
	
	// pos = x*(A+Bi) + y*(E+Si)
	gint<ll> pos=gint<ll>(tx,ty)-P;

	// n := gcd(E+Si,A+Bi) = j*(E+Si) + k*(A+Bi)
	gint<ll> n,j,k;
	n=xgcd(gint<ll>(E,S),gint<ll>(A,B),j,k);

	ll ans=-1;
	if(pos%n==0){
		gint<ll> p=pos/n;
		// x = p*k は一つの解であるが、整数の場合と同じで解はこれだけとは限らない ( mod E+Si の分の任意性がある )
		// |Re(x)|+|Im(x)| が最小となる解 x を見つける
		gint<ll> m=gint<ll>(E,S)/n,t=gint<ll>(A,B)/n;
		// 一般解は x = p*k+l*m, y = p*j-l*t ( l は任意の Gauss 整数 )
		gint<ll> l=-p*k/m;
		ans=INF;
		rep(i,5){
			l.a+=dx[i]; l.b+=dy[i];
			ans=min(ans,llabs((p*k+l*m).a)+llabs((p*k+l*m).b));
			l.a-=dx[i]; l.b-=dy[i];
		}
	}

	P=gint<ll>(tx,ty);

	return ans;
}

Submission Info

Judge Result