oj.uz

Submission #90558

# Submission time Handle Problem Language Result Execution time Memory
90558 2018-12-22T11:53:34 Z popovicirobert Experiments with Gorlum (IZhO13_expgorl) C++14
100 / 100
 4 ms 1032 KB 
#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;
         ^

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 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