Submission #90558

#	Time	Username	Problem	Language	Result	Execution time	Memory
90558		popovicirobert	Experiments with Gorlum (IZhO13_expgorl)	C++14	100 / 100	4 ms	1032 KiB

expgorl

#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 (stderr)

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