Submission #339446

#	Time	Username	Problem	Language	Result	Execution time	Memory
339446		amunduzbaev	Experiments with Gorlum (IZhO13_expgorl)	C++14	100 / 100	13 ms	492 KiB

expgorl

/** made by amunduzbaev **/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/rope>

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class tmp> bool umin(tmp& a, const tmp b) {return a > b? a = b, true:false;}
template<class tmp> bool umax(tmp& a, const tmp b) {return a < b? a = b, true:false;}

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int N = 1e7+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
ll n, m, k, ans, a[N];
ll gx, gy, lx, ly, tx, ty;
string s;

ld dis(int x, int y){ return (ld)sqrt((x - lx) * (x - lx) + (y - ly) * (y - ly)); }

pair<double, double> fx(int cur){
	ld x = gx + cur*tx, y = gy + cur*ty;
	ld mx = 0., mn = mod;
	for(int i=0;i<sz(s);i++){
		if(s[i] == 'L') x--;
		if(s[i] == 'R') x++;
		if(s[i] == 'F') y++;
		if(s[i] == 'B') y--;
		umin(mn, dis(x, y));
		umax(mx, dis(x, y));
	}
	return {mx, mn};
}

double mn(){
	int l = 0, r = k-1;
	while(l+1 < r){
		int m = (l+r)>>1;
		if(fx(m).ss < fx(m+1).ss) r = m;
		else l = m;
	}
	return min(fx(l).ss, fx(r).ss);
}

double mx(){
	return max(fx(0).ff, fx(k-1).ff);
}

void solve(){
	cin>>k>>s;
	cin>>lx>>ly;
	cin>>gx>>gy;
	for(int i=0;i<sz(s);i++){
		if(s[i] == 'L') tx--;
		if(s[i] == 'R') tx++;
		if(s[i] == 'F') ty++;
		if(s[i] == 'B') ty--;
	}
	cout<<fixed<<setprecision(12)<<mn()<<" ";
	cout<<fixed<<setprecision(12)<<mx()<<"\n";
	return;
}


int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

• Subtask 1: 100 / 100