Submission #313323

#	Time	Username	Problem	Language	Result	Execution time	Memory
313323		vitkishloh228	Experiments with Gorlum (IZhO13_expgorl)	C++14	0 / 100	1 ms	384 KiB

expgorl

#include<iostream>
#include<vector>
#include<iomanip>
#include<cmath>
#include<algorithm>
#define int long long 
using namespace std;
struct Vector {
	int x, y;
	Vector() {
		x = 0, y = 0;
	}
	Vector(int a, int b) {
		x = a, y = b;
	}
};
Vector operator+(const Vector& a, const Vector& b) {
	Vector ans;
	ans.x = a.x + b.x;
	ans.y = a.y + b.y;
	return ans;
}
Vector operator*(const Vector& a, int k) {
	Vector ans;
	ans.x = a.x * k;
	ans.y = a.y * k;
	return ans;
}
int getdist(Vector a, int x, int y) {
	//cout << a.x << endl;
	return ((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
}
int32_t main() {
	int k;
	cin >> k;
	//k--;
	string s;
	cin >> s;
	int n = s.size();
	int stx, sty, finx, finy;
	cin >> finx >> finy >> stx >> sty;
	finx -= stx;
	finy -= sty;
	vector<Vector> a(n + 1);
	for (int i = 0; i < n; ++i) {
		a[i + 1] = a[i];
		if (s[i] == 'L') {
			a[i + 1].x--;
		}
		if (s[i] == 'R') {
			a[i + 1].x++;
		}
		if (s[i] == 'F') {
			a[i + 1].y++;
		}
		if (s[i] == 'B') {
			a[i + 1].y--;
		}
		if (s[i] == 'I') {
			//do nothing
		}
	}
	int mind = 1e17, maxd = -1e17;
	for (int i = 0; i < n + 1; ++i) {
		int tl = 0, tr = k + 1;
		while (tl < tr - 2) {
			int tm1 = tl + (tr - tl) / 3;
			int tm2 = tr - (tr - tl) / 3;
			Vector a1 = (a.back() * tm1) + a[i];
			Vector b1 = (a.back() * tm2) + a[i];
			int d1 = getdist(a1, finx, finy);
			int d2 = getdist(b1, finx, finy);
			if (d1 < d2) tl = tm1;
			else tr = tm2;
		}
		int tm = (tl + tr) >> 1;
		Vector a1 = (a.back() * tm) + a[i];
		tm++;
		int d1 = getdist(a1, finx, finy);
		if (tm -1 <= k) {
			mind = min(mind, d1);
			maxd = max(maxd, d1);
		}
		a1 = (a.back() * tm) + a[i];
		d1 = getdist(a1, finx, finy);
		if (tm <= k) {
			mind = min(mind, d1);
			maxd = max(maxd, d1);
		}
		tm = 0;
		a1 = (a.back() * tm) + a[i];
		d1 = getdist(a1, finx, finy);
		mind = min(mind, d1);
		maxd = max(maxd, d1);
		tm = k;
		a1 = (a.back() * tm) + a[i];
		d1 = getdist(a1, finx, finy);
		mind = min(mind, d1);
		maxd = max(maxd, d1);
	}
	
	cout << setprecision(20);
	cout << sqrt(mind + 0.0) << ' ' << sqrt(maxd + 0.000000000000001) << endl;
	//cout << getdist(a[1] * 2, finx, finy);
}

• Subtask 1: 0 / 100