Submission #882106

# Submission time Handle Problem Language Result Execution time Memory
882106 2023-12-02T15:37:31 Z alexdd Experiments with Gorlum (IZhO13_expgorl) C++17
0 / 100
1000 ms 600 KB
#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);
}
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);
    }
    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;
        if(mnm>0 && ((gy-ly>=0 && (gy-ly)+miny<=sq) || ((gy-ly<=0 && (ly-gy)-maxy<=sq))) && ((gx-lx>=0 && (gx-lx)+minx<=sq) || ((gx-lx<=0 && (lx-gx)-maxx<=sq))))
            bl=1;
        if(bl)
        {
            for(int j=0;j<s.size();j++)
            {
                if(s[j]=='L')
                {
                    gx--;
                }
                else if(s[j]=='R')
                {
                    gx++;
                }
                else if(s[j]=='F')
                {
                    gy++;
                }
                else if(s[j]=='B')
                {
                    gy--;
                }
                //if(abs(gx-lx) > 20000 || abs(gy-ly) > 20000)
                  //  break;
                mnm = min(mnm, dist(gx,gy,lx,ly));
                mxm = max(mxm, dist(gx,gy,lx,ly));
            }
        }
        else
        {
            gx += dx;
            gy += dy;
        }
    }
    long double d1 = sqrt(mnm);
    long double d2 = sqrt(mxm);
    cout<<fixed<<setprecision(10)<<d1<<" "<<d2;
    return 0;
}

Compilation message

expgorl.cpp: In function 'int main()':
expgorl.cpp:71:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(int j=0;j<s.size();j++)
      |                         ~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 6 ms 480 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 10 ms 348 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Execution timed out 1096 ms 348 KB Time limit exceeded
18 Halted 0 ms 0 KB -