Submission #16921

#	Time	Username	Problem	Language	Result	Execution time	Memory
16921		murat	Experiments with Gorlum (IZhO13_expgorl)	C++98	100 / 100	62 ms	2264 KiB

expgorl

#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;

int n, m;
double x, y, a, b;
vector< pair< double, double > > v;
string str;

double dist(double x, double y, double a, double b) {
    return sqrt((x-a) * (x-a) + (y-b) * (y-b));
}

double take(double a, double b, int xx) {
    return dist(a + (xx-1) * x, b + (xx-1) * y, ::a, ::b);
}

double find_max(double x, double y) {
    return max(take(x, y, 1), take(x, y, n));
}

double find_min(double x, double y) {
    int bas = 0, son = n;
    while(bas + 5 < son) {
        int l = (son - bas + 1) / 3;
        int o1 = bas + l - 1;
        int o2 = min(son, o1 + l - 1);
        if(take(x, y, o1) >= take(x, y, o2))
            bas = o1;
        else
            son = o2;
    }
    son = min(bas + 300, n);
    bas = max(1, bas - 300);
    double mn = 1e18;
    FOR(i, bas, son)
        mn = min(mn, take(x, y, i));
    return mn;
}


int main() {

    ios_base::sync_with_stdio(false);

    cin >> n;

    cin >> str;
    m = str.size();
    str = '0' + str;

    cin >> a >> b >> x >> y;

    int as = x, ad = y;

    FOR(i, 1, m) {
        v.pb(mp(x, y));
        if(str[i] == 'L') x--;
        if(str[i] == 'R') x++;
        if(str[i] == 'B') y--;
        if(str[i] == 'F') y++;
    } v.pb(mp(x, y));

    x = (x - as);
    y = (y - ad);

    double mx = -1e18, mn = 1e18;

    foreach(it, v)
        mx = max(mx, find_max(it->st, it->nd)),
        mn = min(mn, find_min(it->st, it->nd));

    printf("%.12lf %.12lf\n", mn, mx);

    return 0;
}	

• Subtask 1: 100 / 100