Submission #343213

#	Time	Username	Problem	Language	Result	Execution time	Memory
343213		apostoldaniel854	Experiments with Gorlum (IZhO13_expgorl)	C++14	100 / 100	2 ms	620 KiB

expgorl

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

int k;

ll ans_max, ans_min;
void upd (ll val) {
    if (ans_max < val)
        ans_max = val;
    if (ans_min > val)
        ans_min = val;
}

ll dist (ll x, ll y) {
    return x * x + y * y;
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> k;
    string moves;
    cin >> moves;
    int laser_x, laser_y, gorlum_x, gorlum_y;
    cin >> laser_x >> laser_y;
    cin >> gorlum_x >> gorlum_y;
    gorlum_x -= laser_x;
    gorlum_y -= laser_y;
    vector <pair <int, int>> points;
    int x = 0, y = 0;
    points.pb ({gorlum_x, gorlum_y});
    for (char ch : moves) {
        if (ch == 'L')
            x--;
        if (ch == 'R')
            x++;
        if (ch == 'F')
            y++;
        if (ch == 'B')
            y--;
        points.pb ({x + gorlum_x, y + gorlum_y});
    }
    ans_max = ans_min = dist (gorlum_x, gorlum_y);
    for (pair <int, int> p : points) {
        upd (dist (p.first, p.second));
        upd (dist (p.first + 1ll * (k - 1) * x, p.second + 1ll * (k - 1) * y));
        int best = -1;
        for (int step = (1 << 20); step > 0; step /= 2) {
            if (best + step < k - 1) {
                ll px = p.first + 1ll * (best + step) * x;
                ll py = p.second + 1ll * (best + step) * y;
                if (dist (px, py) >= dist (px + x, py + y))
                    best += step;
            }
        }
        best++;
        upd (dist (p.first + 1ll * best * x, p.second + 1ll * best * y));
    }
    cout << fixed << setprecision (20) << sqrt ((double)ans_min) << " " << sqrt ((double)ans_max) << "\n";
    return 0;
}

• Subtask 1: 100 / 100