oj.uz

Submission #343213

# Submission time Handle Problem Language Result Execution time Memory
343213 2021-01-03T14:28:04 Z apostoldaniel854 Experiments with Gorlum (IZhO13_expgorl) C++14
100 / 100
 2 ms 620 KB 
#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.0 / 100.0

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