제출 #882115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882115		alexdd	생물 실험 (IZhO13_expgorl)	C++17	100 / 100	697 ms	860 KiB

expgorl

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long
const int ct = 10000;
int k;
string s;
int dist(int gx, int gy, int lx, int ly)
{
    return (gx-lx)*(gx-lx) + (gy-ly)*(gy-ly);
}
map<pair<int,int>,int> mp;
vector<pair<int,int>> v;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>k>>s;
    //k = min(k, 40000);
    int gx,gy,lx,ly;
    cin>>lx>>ly>>gx>>gy;
    int mnm = dist(gx,gy,lx,ly), mxm = dist(gx,gy,lx,ly);
    int cpx = gx, cpy = gy;
    int minx=0,maxx=0,miny=0,maxy=0;
    gx=0;
    gy=0;
    for(int i=0;i<(int)s.size();i++)
    {
        if(s[i]=='L')
        {
            gx--;
        }
        else if(s[i]=='R')
        {
            gx++;
        }
        else if(s[i]=='F')
        {
            gy++;
        }
        else if(s[i]=='B')
        {
            gy--;
        }
        minx = min(minx, gx);
        maxx = max(maxx, gx);
        miny = min(miny, gy);
        maxy = max(maxy, gy);
        mp[{gx,gy}]++;
        if(mp[{gx,gy}]==1)
            v.push_back({gx,gy});
    }
    int dx = gx, dy = gy;
    gy = cpy;
    gx = cpx;
    for(int i=0;i<=k;i++)
    {
        mnm=min(mnm,dist(gx+dx*i,gy+dy*i,lx,ly));
        mxm=max(mxm,dist(gx+dx*i,gy+dy*i,lx,ly));
    }
    for(int i=0;i<k;i++)
    {
        ///(gy + cv - ly)^2 <= mnm
        ///abs(gy + cv - ly) <= mnm
        ///
        int sq = (int)sqrt(mnm);
        ///(gy + cv - ly)^2 >= mxm
        bool bl=0;
        if(max((gy + maxy - ly) * (gy + maxy - ly), (gy + miny - ly) * (gy + miny - ly)) + max((gx + maxx - lx) * (gx + maxx - lx), (gx + minx - lx) * (gx + minx - lx)) >= mxm)
            bl=1;
        int rezy = sq + 1,rezx = sq + 1;
        if(gy-ly>=0)
            rezy = max((int)0,(gy-ly)+miny);
        else
            rezy = max((int)0,(ly-gy)-maxy);
        if(gx-lx>=0)
            rezx = max((int)0,(gx-lx)+minx);
        else
            rezx = max((int)0,(lx-gx)-maxx);
        if(mnm>0 && rezx<=sq && rezy<=sq)
            bl=1;
        if(bl)
        {
            for(auto p:v)
            {
                mnm = min(mnm, dist(gx+p.first,gy+p.second,lx,ly));
                mxm = max(mxm, dist(gx+p.first,gy+p.second,lx,ly));
            }
        }
        gx += dx;
        gy += dy;
    }
    long double d1 = sqrt(mnm);
    long double d2 = sqrt(mxm);
    cout<<fixed<<setprecision(10)<<d1<<" "<<d2;
    return 0;
}

• Subtask 1: 100 / 100