Submission #8103

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
8103	2014-08-30T01:09:17 Z	baneling100	Experiments with Gorlum (IZhO13_expgorl)	C++	100 / 100	0 ms	1264 KB

expgorl

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define INF 0x7fffffffffffffff

using namespace std;

long long K, Len, Lx, Ly, Ax, Ay, Vx, Vy, Sx[10001], Sy[10001], MAX, MIN=INF;
char S[10002];

void input(void) {

    scanf("%lld %s %lld %lld %lld %lld",&K,&S[1],&Lx,&Ly,&Ax,&Ay);
    Len=strlen(&S[1]);
}

pair <long long,long long> Order(char T) {

    if(T=='L') return make_pair(-1,0);
    else if(T=='R') return make_pair(1,0);
    else if(T=='F') return make_pair(0,1);
    else if(T=='B') return make_pair(0,-1);
    return make_pair(0,0);
}

void process(void) {

    pair <long long,long long> Temp;
    long long Ex, Ey, Left, Mid1, Mid2, Right, D1, D2;

    Sx[0]=Ax;
    Sy[0]=Ay;
    for(long long i=1 ; i<=Len ; i++) {
        Temp=Order(S[i]);
        Sx[i]=Sx[i-1]+Temp.first;
        Sy[i]=Sy[i-1]+Temp.second;
    }
    Vx=Sx[Len]-Ax;
    Vy=Sy[Len]-Ay;
    for(long long i=0 ; i<=Len ; i++) {
        Ex=Sx[i]+Vx*(K-1);
        Ey=Sy[i]+Vy*(K-1);
        MAX=max(MAX,max((Sx[i]-Lx)*(Sx[i]-Lx)+(Sy[i]-Ly)*(Sy[i]-Ly),(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly)));
        Left=0;
        Right=K-1;
        while(Right-Left>=2) {
            Mid1=(2*Left+Right)/3;
            Mid2=(Left+2*Right)/3;
            Ex=Sx[i]+Vx*Mid1;
            Ey=Sy[i]+Vy*Mid1;
            D1=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
            Ex=Sx[i]+Vx*Mid2;
            Ey=Sy[i]+Vy*Mid2;
            D2=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
            if(D1<D2)
                Right=Mid2-1;
            else
                Left=Mid1+1;
        }
        Ex=Sx[i]+Vx*Left;
        Ey=Sy[i]+Vy*Left;
        D1=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
        Ex=Sx[i]+Vx*Right;
        Ey=Sy[i]+Vy*Right;
        D2=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
        MIN=min(MIN,min(D1,D2));
    }
}

void output(void) {

    printf("%.15lf %.15lf",sqrt(MIN),sqrt(MAX));
}

int main(void) {

    input();
    process();
    output();

    return 0;
}

Subtask #1

100.0 / 100.0

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