oj.uz

Submission #882098

# Submission time Handle Problem Language Result Execution time Memory
882098 2023-12-02T15:25:10 Z alexdd Experiments with Gorlum (IZhO13_expgorl) C++17
0 / 100
 1000 ms 484 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int ct = 15000;
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;
    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--;
        }
        //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));
    }
    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) + 5;


        ///(gy + cv - ly)^2 >= mxm
        bool bl=0;
        if(max((gy + ct - ly) * (gy + ct - ly), (gy - ct - ly) * (gy - ct - ly)) + max((gx + ct - lx) * (gx + ct - lx), (gx - ct - lx) * (gx - ct - 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:69: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]
   69 |             for(int j=0;j<s.size();j++)
      |                         ~^~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 7 ms 348 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 9 ms 448 KB Output is correct
5 Correct 15 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 8 ms 444 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 26 ms 348 KB Output is correct
11 Correct 9 ms 344 KB Output is correct
12 Correct 31 ms 484 KB Output is correct
13 Correct 65 ms 464 KB Output is correct
14 Correct 45 ms 348 KB Output is correct
15 Correct 78 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Execution timed out 1091 ms 348 KB Time limit exceeded
18 Halted 0 ms 0 KB -