Submission #882105

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882105	2023-12-02T15:36:26 Z	alexdd	Experiments with Gorlum (IZhO13_expgorl)	C++17	0 / 100	1000 ms	604 KB

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);
}
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))) && abs(gx-lx)-sq<=max(maxx,-minx))
            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++)
      |                         ~^~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	1 ms	348 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	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	9 ms	476 KB	Output is correct
14	Correct	3 ms	348 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Execution timed out	1094 ms	348 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-