제출 #83738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83738		mra2322001	생물 실험 (IZhO13_expgorl)	C++14	0 / 100	3 ms	500 KiB

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 = 0, r = n, ans = n;
        while(l <= r){
            /// tim min
            int mid = (l + r)/2;
            pii x = d;
            x.first = x.first + mid*1ll*(c.first - b.first);
            x.second = x.second + mid*1ll*(c.second - b.second);
            pii y = d;
            y.first = y.first + (mid + 1)*1ll*(c.first - b.first);
            y.second = y.second + (mid + 1)*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*1ll*(c.first - b.first);
        cur.second = cur.second + ans*1ll*(c.second - b.second);
        res1 = min(res1, dist(cur));
        res2 = max(res2, dist(cur));
        res2 = max(res2, dist(d));
    }
    long double ans1 = res1, ans2 = res2;
    ans1 = sqrt(ans1);
    ans2 = sqrt(ans2);

    cout << fixed << setprecision(10) << ans1 << " ";
    cout << fixed << setprecision(10) << ans2;
}

• Subtask 1: 0 / 100