oj.uz

Submission #930440

# Submission time Handle Problem Language Result Execution time Memory
930440 2024-02-19T15:50:53 Z Karoot Mobile (BOI12_mobile) C++17
100 / 100
 847 ms 50860 KB 
#pragma GCC optimize("Ofast,inline") 
#pragma GCC optimize ("unroll-loops")
 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
vector<pair<double, double> > v;
 
double ending;
 
bool check(double radie){
    vector<double> starts, ends;
 
    for (auto& p : v){
        if (radie < abs(p.second))continue;
        double dx = sqrt(radie*radie - p.second*p.second);
        if (p.first+dx < 0 || p.first-dx > ending || (ends.size() && p.first+dx <= ends.back()))continue;
        while (starts.size() && p.first-dx <= starts.back()){
            starts.pop_back();
            ends.pop_back();
        }
        starts.push_back(p.first-dx);
        ends.push_back(p.first+dx);
    }
 
    int i = 0, j = 0;
 
    int current = 0;
 
    while (i < starts.size() || j < ends.size()){
        if (i == starts.size()){
            current--;
            if (ends[j] <= ending && ends[j] > 0 && !current)return false;
            j++;
 
            continue;
        }
        if (min(starts[i], ends[j]) > 0  && min(starts[i], ends[j]) <= ending && !current)return false;
        if (starts[i] >= ends[j] && ends[j] > ending)break;
        if (starts[i] <= ends[j]){
            i++;
            current++;
        } else {
            j++;
            current--;
        }
    }
 
 
 
    return true;
 
}
 
 
int main(){
    scoobydoobydoo();
    //freopen("mobile.in", "r", stdin);
    int n; cin >> n >> ending;
    double maxi = -1;
    double mini = 1e15;
    for (int i = 0; i < n; i++){
        double x, y; cin >> x >> y;
        if (abs(x-ending) < x){
            maxi = max(maxi, sqrt(x*x + y*y));
            mini = min(mini, sqrt(pow(x-ending, 2) + y*y));
        } else {
            maxi = max(maxi, sqrt(pow(x-ending, 2) + y*y));
            mini = min(mini, sqrt(x*x + y*y));
        }
 
        if (x >= 0 && x <= ending)mini = min(mini, abs(y));


        if (v.size() && x == v.back().first){
            if (abs(v.back().second) > abs(y)){
                v.pop_back();
                v.push_back({x, y});
            }
        } else {
            v.push_back({x, y});
        }
        
    }
 
    cout << fixed << setprecision(10);
    double a = mini, b = maxi+1;
    while (a+(1e-3) < b){
        double k = (a+b)/2.0;
        if (check(k)){
            b = k;
        } else {
            a = k;
        }
    }
 
    cout << a << endl;
 
    _Exit(0);
}

Compilation message

mobile.cpp: In function 'bool check(double)':
mobile.cpp:53:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while (i < starts.size() || j < ends.size()){
      |            ~~^~~~~~~~~~~~~~~
mobile.cpp:53:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while (i < starts.size() || j < ends.size()){
      |                                 ~~^~~~~~~~~~~~~
mobile.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (i == starts.size()){
      |             ~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 3 ms 604 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 4 ms 604 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4676 KB Output is correct
2 Correct 37 ms 2512 KB Output is correct
3 Correct 26 ms 3032 KB Output is correct
4 Correct 32 ms 3676 KB Output is correct
5 Correct 15 ms 856 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1368 KB Output is correct
2 Correct 32 ms 2208 KB Output is correct
3 Correct 31 ms 3536 KB Output is correct
4 Correct 33 ms 3536 KB Output is correct
5 Correct 37 ms 3712 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5408 KB Output is correct
2 Correct 38 ms 2520 KB Output is correct
3 Correct 40 ms 3796 KB Output is correct
4 Correct 56 ms 3964 KB Output is correct
5 Correct 29 ms 2008 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3272 KB Output is correct
2 Correct 50 ms 3136 KB Output is correct
3 Correct 33 ms 1924 KB Output is correct
4 Correct 50 ms 4012 KB Output is correct
5 Correct 38 ms 3640 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6280 KB Output is correct
2 Correct 42 ms 2780 KB Output is correct
3 Correct 33 ms 1940 KB Output is correct
4 Correct 52 ms 4044 KB Output is correct
5 Correct 40 ms 3748 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 26564 KB Output is correct
2 Correct 181 ms 8520 KB Output is correct
3 Correct 172 ms 7832 KB Output is correct
4 Correct 223 ms 18072 KB Output is correct
5 Correct 191 ms 14520 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 9504 KB Output is correct
2 Correct 350 ms 28300 KB Output is correct
3 Correct 188 ms 8700 KB Output is correct
4 Correct 220 ms 17804 KB Output is correct
5 Correct 204 ms 15604 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 34408 KB Output is correct
2 Correct 211 ms 9900 KB Output is correct
3 Correct 262 ms 9832 KB Output is correct
4 Correct 291 ms 28028 KB Output is correct
5 Correct 257 ms 16060 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 10580 KB Output is correct
2 Correct 408 ms 38064 KB Output is correct
3 Correct 195 ms 9308 KB Output is correct
4 Correct 279 ms 27644 KB Output is correct
5 Correct 253 ms 27736 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 37480 KB Output is correct
2 Correct 281 ms 11400 KB Output is correct
3 Correct 238 ms 10720 KB Output is correct
4 Correct 314 ms 27320 KB Output is correct
5 Correct 252 ms 19248 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12212 KB Output is correct
2 Correct 481 ms 41012 KB Output is correct
3 Correct 243 ms 12036 KB Output is correct
4 Correct 316 ms 28304 KB Output is correct
5 Correct 289 ms 27556 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 43064 KB Output is correct
2 Correct 303 ms 12880 KB Output is correct
3 Correct 273 ms 12484 KB Output is correct
4 Correct 363 ms 29868 KB Output is correct
5 Correct 302 ms 19804 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 13704 KB Output is correct
2 Correct 531 ms 44696 KB Output is correct
3 Correct 268 ms 13220 KB Output is correct
4 Correct 358 ms 30472 KB Output is correct
5 Correct 378 ms 27976 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 47000 KB Output is correct
2 Correct 357 ms 16208 KB Output is correct
3 Correct 343 ms 15184 KB Output is correct
4 Correct 459 ms 36092 KB Output is correct
5 Correct 370 ms 21104 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 17092 KB Output is correct
2 Correct 655 ms 50860 KB Output is correct
3 Correct 340 ms 17580 KB Output is correct
4 Correct 483 ms 36072 KB Output is correct
5 Correct 395 ms 30500 KB Output is correct