Submission #226362

#	Time	Username	Problem	Language	Result	Execution time	Memory
226362		emil_physmath	Experiments with Gorlum (IZhO13_expgorl)	C++17	100 / 100	6 ms	512 KiB

expgorl

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
using llong = long long;
struct Vec
{
    llong x, y;
    llong len() const { return x * x + y * y; }
    Vec operator-() const { return {-x, -y}; }
};
Vec operator+(const Vec& a, const Vec& b) { return {a.x + b.x, a.y + b.y}; }
Vec operator-(const Vec& a, const Vec& b) { return a + -b; }
Vec operator*(llong k, const Vec& a) { return {k * a.x, k * a.y}; }
bool operator<(const Vec& a, const Vec& b) { return a.len() < b.len(); }

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int k;
    cin >> k;
    string temp;
    cin >> temp;
    Vec s, e;
    cin >> e.x >> e.y >> s.x >> s.y;
    vector<Vec> a(temp.length());
    for (int i = 0; i < temp.length(); ++i)
    {
        if (i) a[i] = a[i - 1];
        else a[i] = {0, 0};
        if (temp[i] == 'L') --a[i].x;
        else if (temp[i] == 'R') ++a[i].x;
        else if (temp[i] == 'F') ++a[i].y;
        else if (temp[i] == 'B') --a[i].y;
    }
    Vec mn = e + -s, mx = e + -s;
    for (int i = 0; i < a.size(); ++i)
    {
        auto Go = [&a, &i, &s, &e](int p) -> Vec { return e - (s + p * a.back() + a[i]); };
        int l = 0, r = k - 1;
        int m = -1;
        while (l <= r)
        {
            int curm = (l + r) / 2;
            if (Go(curm) < Go(curm - 1))
            {
                m = curm;
                l = curm + 1;
            }
            else
                r = curm - 1;
        }
        mx = max(mx, Go(0));
        mx = max(mx, Go(k - 1));
#ifdef MANSON
        cerr << "i: " << i << ", mx = " << mx.len() << '\n';
#endif
        if (m != -1)
            mn = min(mn, Go(m));
        if (m + 1 <= k - 1)
            mn = min(mn, Go(m + 1));
    }
    cout.precision(10);
    cout << fixed << sqrt(mn.len()) << ' ' << sqrt(mx.len());
}

Compilation message (stderr)

expgorl.cpp: In function 'int main()':
expgorl.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < temp.length(); ++i)
                     ~~^~~~~~~~~~~~~~~
expgorl.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~

• Subtask 1: 100 / 100