oj.uz

Submission #305634

# Submission time Handle Problem Language Result Execution time Memory
305634 2020-09-23T17:44:33 Z ant101 Mobile (BOI12_mobile) C++14
100 / 100
 912 ms 51936 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
using namespace std;


#define rep(x,a)           for(int x = 0; x < a; x++)
#define REP(x,a,b)         for(int x = a; x < b; x++)
#define per(x,b)           for(int x = b; x >= 0; x--)
#define all(container)     (container).begin(), container.end()
#define rall(container)    (container).rbegin(), container.rend()
#define sz(container)      (int) (container).size()
#define pb                 push_back
#define eb                 emplace_back
#define fi                 first
#define sc                 second

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T> bool smin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool smax(T &a, T b) { return a < b ? (a = b, true) : false; }

#ifdef LOCAL_DEFINE
#include "DEBUG.hpp"
#else
#define debug(...) 0
#endif

const double eps = 1e-3;
const double EPS = 1e-9;

bool eq(double a, double b) {
    return abs(a-b) <= eps;
}

int main(void)
{
    int n;
    double last;
    scanf("%d%lf", &n, &last);
    vector<pair<double, double>> points(n);
    rep(i,n) scanf("%lf%lf", &points[i].fi, &points[i].sc);
    vector<pair<double, double>> poi;
    rep(i,n) {
        poi.emplace_back(points[i]);
        ++i;
        while (i < n && eq(points[i].fi, poi.back().fi)) ++i;
        --i;
    }
    auto Can = [&](double dist) {
        double r = 0.0;
        rep(i,n) {
            double delta = sqrt(dist*dist-points[i].sc*points[i].sc);
            double L = points[i].fi-delta, R = points[i].fi+delta;
            if (L <= r) smax(r, R);
        }
        return (r >= last);
    };
    double l = 0.0, r = 1e10;
    while (r-l > eps) {
        double mid = (r+l)/2.0;
        if (Can(mid)) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d%lf", &n, &last);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
mobile.cpp:58:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     rep(i,n) scanf("%lf%lf", &points[i].fi, &points[i].sc);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 640 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 5 ms 640 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 512 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4460 KB Output is correct
2 Correct 47 ms 3696 KB Output is correct
3 Correct 38 ms 2928 KB Output is correct
4 Correct 62 ms 4844 KB Output is correct
5 Correct 36 ms 1536 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2424 KB Output is correct
2 Correct 54 ms 3440 KB Output is correct
3 Correct 64 ms 4844 KB Output is correct
4 Correct 65 ms 4916 KB Output is correct
5 Correct 77 ms 5356 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4588 KB Output is correct
2 Correct 50 ms 3952 KB Output is correct
3 Correct 54 ms 4844 KB Output is correct
4 Correct 91 ms 5996 KB Output is correct
5 Correct 64 ms 3324 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4600 KB Output is correct
2 Correct 61 ms 4464 KB Output is correct
3 Correct 60 ms 3324 KB Output is correct
4 Correct 90 ms 5996 KB Output is correct
5 Correct 78 ms 5364 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5612 KB Output is correct
2 Correct 58 ms 4468 KB Output is correct
3 Correct 60 ms 3320 KB Output is correct
4 Correct 89 ms 5996 KB Output is correct
5 Correct 78 ms 5356 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 19428 KB Output is correct
2 Correct 300 ms 11896 KB Output is correct
3 Correct 301 ms 11128 KB Output is correct
4 Correct 441 ms 18916 KB Output is correct
5 Correct 389 ms 19172 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 11332 KB Output is correct
2 Correct 391 ms 19172 KB Output is correct
3 Correct 303 ms 13036 KB Output is correct
4 Correct 445 ms 19172 KB Output is correct
5 Correct 404 ms 19172 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 29280 KB Output is correct
2 Correct 351 ms 13572 KB Output is correct
3 Correct 354 ms 12664 KB Output is correct
4 Correct 540 ms 28384 KB Output is correct
5 Correct 467 ms 26084 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 12408 KB Output is correct
2 Correct 468 ms 28896 KB Output is correct
3 Correct 361 ms 14444 KB Output is correct
4 Correct 540 ms 28384 KB Output is correct
5 Correct 482 ms 35040 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 30680 KB Output is correct
2 Correct 412 ms 14328 KB Output is correct
3 Correct 420 ms 21624 KB Output is correct
4 Correct 629 ms 41440 KB Output is correct
5 Correct 535 ms 28644 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 13704 KB Output is correct
2 Correct 546 ms 37052 KB Output is correct
3 Correct 434 ms 21868 KB Output is correct
4 Correct 621 ms 41312 KB Output is correct
5 Correct 576 ms 38112 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 32224 KB Output is correct
2 Correct 475 ms 16248 KB Output is correct
3 Correct 488 ms 24696 KB Output is correct
4 Correct 726 ms 45280 KB Output is correct
5 Correct 639 ms 32504 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 16720 KB Output is correct
2 Correct 629 ms 40160 KB Output is correct
3 Correct 487 ms 24556 KB Output is correct
4 Correct 715 ms 44896 KB Output is correct
5 Correct 645 ms 41056 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 35732 KB Output is correct
2 Correct 601 ms 31736 KB Output is correct
3 Correct 605 ms 30840 KB Output is correct
4 Correct 899 ms 51808 KB Output is correct
5 Correct 781 ms 37860 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 22904 KB Output is correct
2 Correct 784 ms 45916 KB Output is correct
3 Correct 639 ms 32616 KB Output is correct
4 Correct 912 ms 51936 KB Output is correct
5 Correct 818 ms 47328 KB Output is correct