oj.uz

Submission #339334

# Submission time Handle Problem Language Result Execution time Memory
339334 2020-12-25T05:15:52 Z talant117408 Experiments with Gorlum (IZhO13_expgorl) C++17
100 / 100
 933 ms 2664 KB 
/*
    Code written by Talant I.D.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

struct point{
    double x, y;
};

bool cmp(pair <double, point> a, pair <double, point> b){
    return a.first < b.first;
}

int main(){
    do_not_disturb
    
    int k;
    string s;
    point laser, gor, gor_next;
    cin >> k >> s >> laser.x >> laser.y >> gor.x >> gor.y;
    
    gor_next = gor;
    
    for(auto to : s){
        if(to == 'L') gor_next.x--;
        else if(to == 'R') gor_next.x++;
        else if(to == 'F') gor_next.y++;
        else if(to == 'B') gor_next.y--;
    }
    
    gor_next.x -= gor.x;
    gor_next.y -= gor.y;
        
    vector <point> candidates;
    
    for(double i = 0; i < k; i++){
        point nxt;
        nxt.x = gor.x+gor_next.x*i;
        nxt.y = gor.y+gor_next.y*i;
        candidates.pb(nxt);
    }
    
    double mn = 1000000000000ll, mx = 0;
  
    for(int i = 0; i < min(1001, k); i++){
        auto it1 = candidates[i];
        mn = min(mn, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
        mx = max(mx, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
        for(auto to : s){
            if(to == 'L') it1.x--;
            else if(to == 'R') it1.x++;
            else if(to == 'F') it1.y++;
            else if(to == 'B') it1.y--;
            mn = min(mn, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
            mx = max(mx, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
        }
    }
    for(int i = max(1001, k-1000); i < k; i++){
        auto it1 = candidates[i];
        mn = min(mn, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
        mx = max(mx, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
        for(auto to : s){
            if(to == 'L') it1.x--;
            else if(to == 'R') it1.x++;
            else if(to == 'F') it1.y++;
            else if(to == 'B') it1.y--;
            mn = min(mn, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
            mx = max(mx, hypot(fabs(it1.x-laser.x), fabs(it1.y-laser.y)));
        }
    }
    
    
    cout << precision(12) << mn << ' ' << mx;
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1008 KB Output is correct
2 Correct 149 ms 752 KB Output is correct
3 Correct 164 ms 752 KB Output is correct
4 Correct 169 ms 748 KB Output is correct
5 Correct 103 ms 748 KB Output is correct
6 Correct 122 ms 1008 KB Output is correct
7 Correct 169 ms 748 KB Output is correct
8 Correct 169 ms 1008 KB Output is correct
9 Correct 550 ms 2532 KB Output is correct
10 Correct 817 ms 2536 KB Output is correct
11 Correct 468 ms 2536 KB Output is correct
12 Correct 871 ms 1516 KB Output is correct
13 Correct 879 ms 1536 KB Output is correct
14 Correct 689 ms 2532 KB Output is correct
15 Correct 652 ms 2532 KB Output is correct
16 Correct 782 ms 2536 KB Output is correct
17 Correct 731 ms 2536 KB Output is correct
18 Correct 933 ms 2536 KB Output is correct
19 Correct 908 ms 2664 KB Output is correct
20 Correct 889 ms 2536 KB Output is correct