Submission #83741

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
83741	2018-11-10T09:24:28 Z	mra2322001	Experiments with Gorlum (IZhO13_expgorl)	C++14	100 / 100	3 ms	932 KB

expgorl

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
#define mu2(x) ((x)*(1ll)*(x))

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 10002;

int n;
pii a, b, c;
string s;

ll dist(pii cur){
    /// cur -> a
    ll res = mu2(a.first - cur.first) + mu2(a.second - cur.second);
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
  
    cin >> n;
    cin >> s;
    s = " " + s;
    int len = s.length() - 1;
    cin >> a.first >> a.second;
    cin >> b.first >> b.second;

    c = b;
    f1(i, len){
        if(s[i]=='L') c.first--;
        if(s[i]=='R') c.first++;
        if(s[i]=='F') c.second++;
        if(s[i]=='B') c.second--;
    }

    ll res1 = LLONG_MAX, res2 = 0;
    pii d = b;
    f0(i, len + 1){
        if(i != 0){
            if(s[i]=='L') d.first--;
            if(s[i]=='R') d.first++;
            if(s[i]=='F') d.second++;
            if(s[i]=='B') d.second--;
        }
        int l = 1, r = n, ans = n;
        while(l <= r){
            /// tim min
            int mid = (l + r)/2;
            pii x = d;
            x.first = x.first + (mid - 1)*1ll*(c.first - b.first);
            x.second = x.second + (mid - 1)*1ll*(c.second - b.second);
            pii y = d;
            y.first = y.first + (mid)*1ll*(c.first - b.first);
            y.second = y.second + (mid)*1ll*(c.second - b.second);
            if(dist(x) < dist(y)) r = mid - 1, ans = mid;
            else l = mid + 1;
        }
        pii cur = d;
        cur.first = cur.first + (ans - 1)*1ll*(c.first - b.first);
        cur.second = cur.second + (ans - 1)*1ll*(c.second - b.second);
        res1 = min(res1, dist(cur));
        res2 = max(res2, dist(d));
        cur = d;
        cur.first = cur.first + (n - 1)*1ll*(c.first - b.first);
        cur.second = cur.second + (n - 1)*1ll*(c.second - b.second);
        res2 = max(res2, dist(cur));
    }
    long double ans1 = res1, ans2 = res2;
    ans1 = sqrt(ans1);
    ans2 = sqrt(ans2);
    cout << fixed << setprecision(12);
    cout << ans1 << " " << ans2 << endl;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct
4	Correct	2 ms	568 KB	Output is correct
5	Correct	2 ms	568 KB	Output is correct
6	Correct	2 ms	568 KB	Output is correct
7	Correct	2 ms	568 KB	Output is correct
8	Correct	2 ms	596 KB	Output is correct
9	Correct	2 ms	600 KB	Output is correct
10	Correct	3 ms	780 KB	Output is correct
11	Correct	2 ms	780 KB	Output is correct
12	Correct	3 ms	780 KB	Output is correct
13	Correct	3 ms	900 KB	Output is correct
14	Correct	3 ms	900 KB	Output is correct
15	Correct	3 ms	900 KB	Output is correct
16	Correct	3 ms	900 KB	Output is correct
17	Correct	3 ms	900 KB	Output is correct
18	Correct	3 ms	900 KB	Output is correct
19	Correct	3 ms	916 KB	Output is correct
20	Correct	3 ms	932 KB	Output is correct