#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int MAXK = (int) 1e5;
char dx[256], dy[256];
inline ll dist(ll x, ll y) {
return 1LL * x * x + 1LL * y * y;
}
string str;
int lx, ly, gx, gy;
double mn = 1e18, mx = 0;
inline void upd(ll cur) {
mn = min(mn, 1.0 * cur);
mx = max(mx, 1.0 * cur);
}
inline void solve(vector < pair <int, int> > pts, int k, int x, int y) {
for(auto it : pts) {
upd(dist(it.first, it.second));
upd(dist(it.first + 1LL * k * x, it.second + 1LL * k * y));
int res = -1;
for(int step = 1 << 16; step; step >>= 1) {
if(res + step < k && dist(it.first + 1LL * (res + step) * x, it.second + 1LL * (res + step) * y) >= dist(it.first + 1LL * (res + step + 1) * x, it.second + 1LL * (res + step + 1) * y)) {
res += step;
}
}
res++;
upd(dist(it.first + 1LL * res * x, it.second + 1LL * res * y));
}
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> k >> str;
int lx, ly, gx, gy;
cin >> lx >> ly >> gx >> gy;
gx -= lx, gy -= ly;
dx['L'] = -1, dx['R'] = 1;
dy['F'] = 1, dy['B'] = -1;
vector < pair <int, int> > pts;
int x = gx, y = gy;
pts.push_back({x, y});
for(auto it : str) {
x += dx[it], y += dy[it];
pts.push_back({x, y});
}
solve(pts, k - 1, x - gx, y - gy);
mn = sqrt(mn), mx = sqrt(mx);
cout << fixed << setprecision(20) << mn << " " << mx;
//cin.close();
//cout.close();
return 0;
}
Compilation message
expgorl.cpp: In function 'int main()':
expgorl.cpp:59:19: warning: array subscript has type 'char' [-Wchar-subscripts]
x += dx[it], y += dy[it];
^
expgorl.cpp:59:32: warning: array subscript has type 'char' [-Wchar-subscripts]
x += dx[it], y += dy[it];
^
expgorl.cpp:46:9: warning: unused variable 'i' [-Wunused-variable]
int i, k;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
436 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
608 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
2 ms |
628 KB |
Output is correct |
7 |
Correct |
2 ms |
628 KB |
Output is correct |
8 |
Correct |
2 ms |
644 KB |
Output is correct |
9 |
Correct |
3 ms |
764 KB |
Output is correct |
10 |
Correct |
3 ms |
772 KB |
Output is correct |
11 |
Correct |
2 ms |
804 KB |
Output is correct |
12 |
Correct |
3 ms |
860 KB |
Output is correct |
13 |
Correct |
3 ms |
1016 KB |
Output is correct |
14 |
Correct |
4 ms |
1016 KB |
Output is correct |
15 |
Correct |
3 ms |
1016 KB |
Output is correct |
16 |
Correct |
3 ms |
1016 KB |
Output is correct |
17 |
Correct |
2 ms |
1016 KB |
Output is correct |
18 |
Correct |
3 ms |
1016 KB |
Output is correct |
19 |
Correct |
3 ms |
1020 KB |
Output is correct |
20 |
Correct |
3 ms |
1032 KB |
Output is correct |