oj.uz

Submission #339487

# Submission time Handle Problem Language Result Execution time Memory
339487 2020-12-25T13:32:25 Z tengiz05 Experiments with Gorlum (IZhO13_expgorl) C++17
100 / 100
 12 ms 492 KB 
/** 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<<mn()<<" "<<mx()<<"\n";
	return;
}
 
 
int main(){
	fastios
      cout<<fixed<<setprecision(12);
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 5 ms 364 KB Output is correct
10 Correct 8 ms 492 KB Output is correct
11 Correct 4 ms 364 KB Output is correct
12 Correct 8 ms 364 KB Output is correct
13 Correct 12 ms 492 KB Output is correct
14 Correct 7 ms 364 KB Output is correct
15 Correct 6 ms 364 KB Output is correct
16 Correct 6 ms 364 KB Output is correct
17 Correct 7 ms 364 KB Output is correct
18 Correct 8 ms 364 KB Output is correct
19 Correct 9 ms 364 KB Output is correct
20 Correct 9 ms 364 KB Output is correct