Submission #882101

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882101	2023-12-02T15:28:44 Z	alexdd	Experiments with Gorlum (IZhO13_expgorl)	C++17	0 / 100	1000 ms	480 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(abs(gy-ly)-sq<=ct && abs(gx-lx)-sq<=ct)
            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	2 ms	348 KB	Output is correct
2	Correct	3 ms	348 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	4 ms	348 KB	Output is correct
5	Correct	9 ms	344 KB	Output is correct
6	Correct	3 ms	348 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	3 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	10 ms	480 KB	Output is correct
11	Correct	4 ms	348 KB	Output is correct
12	Correct	12 ms	476 KB	Output is correct
13	Correct	31 ms	348 KB	Output is correct
14	Correct	10 ms	348 KB	Output is correct
15	Correct	21 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Execution timed out	1025 ms	344 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-