Submission #339297

#	Time	Username	Problem	Language	Result	Execution time	Memory
339297		tengiz05	Experiments with Gorlum (IZhO13_expgorl)	C++17	100 / 100	582 ms	640 KiB

expgorl

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
string s;
ld ansmn, ansmx;
int go1[5] = {1, -1, 0, 0, 0};
int go2[5] = {0, 0, 1, -1, 0};
int dir[N];
ld dist(int x1, int y1, int x2, int y2){
	return (ld)sqrtl((ld)abs(x1-x2)*abs(x1-x2) + (ld)abs(y1-y2)*abs(y1-y2));
}

int aftergy, aftergx;
pii doit(int dx, int dy, int gx, int gy){
	ckmin(ansmn, dist(dx, dy, gx, gy));
	ckmax(ansmx, dist(dx, dy, gx, gy));
	ld mn = mod*mod, mx = 0.;
	for(int i=0;i<n;i++){
		gx += go1[dir[i]];
		gy += go2[dir[i]];
		ckmin(ansmn, dist(dx, dy, gx, gy));
		ckmax(ansmx, dist(dx, dy, gx, gy));
		
		ckmin(mn, dist(dx, dy, gx, gy));
		ckmax(mx, dist(dx, dy, gx, gy));
		
	}
	aftergy = gy;
	aftergx = gx;
	return {mn, mx};
}

void solve(int test_case){
	cout << fixed << setprecision(12);
	int i, j;
	cin >> k;
	cin >> s;
	n = s.length();
	for(i=0;i<n;i++){
		if(s[i] == 'L')dir[i] = 1;
		if(s[i] == 'R')dir[i] = 0;
		if(s[i] == 'F')dir[i] = 2;
		if(s[i] == 'B')dir[i] = 3;
		if(s[i] == 'I')dir[i] = 4;
	}
	int dx, dy;
	int gx, gy;
	cin >> dx >> dy;
	cin >> gx >> gy;
	ansmn = mod*mod;
	ansmx = 0.;
	
	int deltax, deltay;
	pii I_DONT_EVEN_NEED_IT = doit(dx, dy, gx, gy);
	deltax = aftergx - gx;
	deltay = aftergy - gy;
	
	int l = 1, r = k-1;
	int itr = 0;
	while(l < r){
		itr++;
		if(itr > 300)break;
		int mid = (l+r)/2;
		int tox = gx + deltax * mid;
		int toy = gy + deltay * mid;
		auto [mn1, mx1] = doit(dx, dy, tox, toy);
		tox -= deltax;
		toy -= deltay;
		auto [mn2, mx2] = doit(dx, dy, tox, toy);
		if(mn2 < mn1){
			r = mid;
		}else l = mid;
	}
	doit(dx, dy, gx+deltax*(k-1), gy+deltay*(k-1));
//	cout << l << ' ' << r << '\n';
	//~ for(i=0;i<k;i++){
		//~ doit(dx, dy, gx, gy);
		//~ gx = aftergx;
		//~ gy = aftergy;
	//~ }
	for(i=max(0ll, l-1000); i < min(k, r+1000); i++){
		int tox = gx + deltax * i;
		int toy = gy + deltay * i;
		doit(dx, dy, tox, toy);
	}
	l = 1, r = k-1;
	itr = 0;
	while(l < r){
		itr++;
		if(itr > 300)break;
		int mid = (l+r)/2;
		int tox = gx + deltax * mid;
		int toy = gy + deltay * mid;
		auto [mn1, mx1] = doit(dx, dy, tox, toy);
		tox -= deltax;
		toy -= deltay;
		auto [mn2, mx2] = doit(dx, dy, tox, toy);
		if(mx2 > mx1){
			r = mid;
		}else l = mid;
	}
	for(i=max(0ll, l-1000); i < min(k, r+1000); i++){
		int tox = gx + deltax * i;
		int toy = gy + deltay * i;
		doit(dx, dy, tox, toy);
	}
//	cout << l << ' ' << r << '\n';
	
	cout << ansmn << ' ' << ansmx << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message (stderr)

expgorl.cpp: In function 'void solve(long long int)':
expgorl.cpp:48:9: warning: unused variable 'j' [-Wunused-variable]
   48 |  int i, j;
      |         ^
expgorl.cpp:67:6: warning: variable 'I_DONT_EVEN_NEED_IT' set but not used [-Wunused-but-set-variable]
   67 |  pii I_DONT_EVEN_NEED_IT = doit(dx, dy, gx, gy);
      |      ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100