Submission #2518923

---

Source Code Expand

// #include "grader.cpp"
#include <vector>
#include <queue>
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
struct complex {ll x,y;};

complex red;
complex prev;

void print(complex c){
	cout << c.x << (c.y >= 0 ? "+" : "") << c.y << "i" << ' ';
}

complex product(complex x, complex y){
	complex ans = {x.x * y.x - x.y * y.y, x.x * y.y + x.y * y.x};
	return ans;
}

ll round(double x){
	if(x >= 0) return (ll)(x + 0.5);
	return -round(-x);
}

void divide(complex x, complex y, complex &quotient, complex &remainder){ // x / y
	ll a = round((double)(x.x * y.x + x.y * y.y) / (y.x * y.x + y.y * y.y));
	ll b = round((double)(-x.x * y.y + x.y * y.x) / (y.x * y.x + y.y * y.y));
	quotient.x = a; quotient.y = b;
	complex tmp = product(y,quotient);
	remainder.x = x.x - tmp.x; remainder.y = x.y - tmp.y;
}

void extended_gcd(complex x, complex y, complex &a, complex &b, complex &g){ // ax + by = g
//	print(x); print(y); print(a); print(b); print(g);
//	cout << endl;
	
	if(x.x == 0 && x.y == 0){
		a.x = a.y = b.y = 0; b.x = 1; g = y;
		return;
	}
	
	complex q,r;
	divide(y,x,q,r);
	
	complex p1,p2;
	extended_gcd(r,x,p1,p2,g);
	complex p3 = product(q,p1);
	a.x = p2.x - p3.x; a.y = p2.y - p3.y;
	b = p1;
	
//	cout << "ext gcd: ";
//	print(x); print(y); print(a); print(b); print(g);
//	cout << endl;
}

ll func(complex red, complex black, complex blue){
//	cout << "A"; print(red); print(black); print(blue); cout << endl;
	
	complex a,b,g;
	extended_gcd(black,red,a,b,g);
	
//	cout << "A"; print(a); print(b); print(g); cout << endl;
	
	complex q,r;
	divide(blue,g,q,r);
	if(r.x != 0 || r.y != 0) return -1;
	complex ans = product(a,q);
	
//	cout << "A"; print(ans); cout << endl;
	
	divide(red,g,q,r);
	complex modulo = q;
	
//	cout << "A"; print(modulo); cout << endl;
	
	divide(ans,modulo,q,r);
	ans = r;
	
//	cout << "A"; print(ans); cout << endl;
	
	ll ans2 = (1ll<<60);
	
	int i,j;
	
	for(i=-3;i<=3;i++) for(j=-3;j<=3;j++){
		complex c = {i,j};
		complex d = product(c,modulo);
		ll dx = ans.x - d.x, dy = ans.y - d.y;
		if(dx < 0) dx = -dx; if(dy < 0) dy = -dy;
		ans2 = min(ans2,dx+dy);
	}
	
	return ans2;
}

void init(int E, int S)
{
	red.x = E; red.y = S;
	prev.x = 0; prev.y = 0;
}

int moveTo(int X, int Y, int A, int B)
{
	complex blue = {X - prev.x, Y - prev.y};
	prev.x = X; prev.y = Y;
	complex black = {A, B};
	ll ans = func(red, black, blue);
	return (int)ans;
}

Submission Info

Compile Error

/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 0 has invalid symbol index 11
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 1 has invalid symbol index 12
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 2 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 3 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 4 has invalid symbol index 11
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 5 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 6 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 7 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 8 has invalid symbol ...