oj.uz

Submission #407329

# Submission time Handle Problem Language Result Execution time Memory
407329 2021-05-18T18:13:01 Z phisti Mobile (BOI12_mobile) C++17
100 / 100
 980 ms 35428 KB 
// https://oj.uz/problem/view/BOI12_mobile
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <queue>
#include <math.h>

#define sz(x)   (int)size(x)
#define last_elem(coll) (*(coll.rbegin()))
#define FOR(x, e) for(u32 x = 0; x < (u32)(e); x++)
#define FORR(x, e) for(u32 x = (u32)(e) - 1; x < (u32)(e); x--)
#define FOB(x, b, e) for(auto x = (b); x != (e); x++)
#define FOI(x, e, i) for(u32 x = 0; x < (u32)e; x += (u32)(i))
#define FORE(x, C) for(auto& x: C)

using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i16 = short;
using u16 = unsigned short;
using i8 = char;
using u8 = unsigned char;
using f64 = double;
using f32 = float;
using si = i32;
using sl = i64;
using ui = u32;
using ul = u64;
using vsl = std::vector<i64>;
using vsi = std::vector<i32>;
using vss = std::vector<i16>;
using vul = std::vector<u64>;
using vui = std::vector<u32>;
using vus = std::vector<u16>;

#ifdef MY_COMPILE
auto stin = std::ifstream("TestSamples/BIO12_Mobile-oj.in");
auto sout = std::ofstream("TestSamples/BIO12_Mobile-oj.out");
#elif OLDERN
auto stin = std::ifstream("bcount.in");
auto sout = std::ofstream("bcount.out");
#else
auto &stin = std::cin;
auto &sout = std::cout;
#endif

bool is_covered(
    vector<pair<sl, sl>>& towers,
    double power,
    sl length)
{
    auto p2 = power * power;
    double last = 0;
    FORE(t, towers) {
        if (p2 < t.second) continue;
        auto dist = sqrt(p2 - t.second);
        if (t.first - dist <= last) last = max(t.first  + dist, last);
    }
    
    return last >= length;
}

int main()
{
    ul N, L;
    stin >> N >> L;
    
    vector<pair<sl, sl>> towers(N);
    
    FORE(p, towers) stin >> p.first >> p.second;
    
    sl maxY = 0;
    FORE(p, towers) {
        maxY = max(maxY, abs(p.second) + abs(p.first));
        p.second = p.second * p.second;
    }
    
    double in = 0, ax = maxY + L;
    while(ax - in > 0.0000001) {
        auto ean = in + (ax - in) / 2;
        if (is_covered(towers, ean, L)) {
            ax = ean;
        } else {
            in = ean;
        }
    }
    
    sout.precision(5);
    sout << fixed << ax;

    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 5 ms 440 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1464 KB Output is correct
2 Correct 68 ms 2508 KB Output is correct
3 Correct 44 ms 1636 KB Output is correct
4 Correct 64 ms 2640 KB Output is correct
5 Correct 29 ms 1456 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1508 KB Output is correct
2 Correct 50 ms 2152 KB Output is correct
3 Correct 61 ms 2572 KB Output is correct
4 Correct 67 ms 2676 KB Output is correct
5 Correct 78 ms 3048 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 1612 KB Output is correct
2 Correct 75 ms 1568 KB Output is correct
3 Correct 65 ms 1616 KB Output is correct
4 Correct 95 ms 1836 KB Output is correct
5 Correct 59 ms 2500 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1740 KB Output is correct
2 Correct 87 ms 1740 KB Output is correct
3 Correct 75 ms 1860 KB Output is correct
4 Correct 97 ms 1844 KB Output is correct
5 Correct 74 ms 2988 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1740 KB Output is correct
2 Correct 88 ms 1740 KB Output is correct
3 Correct 71 ms 1740 KB Output is correct
4 Correct 98 ms 1868 KB Output is correct
5 Correct 75 ms 3004 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 8116 KB Output is correct
2 Correct 467 ms 8132 KB Output is correct
3 Correct 436 ms 8108 KB Output is correct
4 Correct 472 ms 8012 KB Output is correct
5 Correct 399 ms 14944 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 8112 KB Output is correct
2 Correct 487 ms 8112 KB Output is correct
3 Correct 370 ms 13868 KB Output is correct
4 Correct 473 ms 17448 KB Output is correct
5 Correct 417 ms 15408 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 9676 KB Output is correct
2 Correct 562 ms 9676 KB Output is correct
3 Correct 528 ms 9676 KB Output is correct
4 Correct 585 ms 9688 KB Output is correct
5 Correct 460 ms 17728 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 9672 KB Output is correct
2 Correct 576 ms 9680 KB Output is correct
3 Correct 465 ms 16432 KB Output is correct
4 Correct 586 ms 21448 KB Output is correct
5 Correct 485 ms 18384 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 11236 KB Output is correct
2 Correct 650 ms 11212 KB Output is correct
3 Correct 614 ms 11244 KB Output is correct
4 Correct 678 ms 11248 KB Output is correct
5 Correct 533 ms 20552 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 11244 KB Output is correct
2 Correct 663 ms 11240 KB Output is correct
3 Correct 542 ms 19764 KB Output is correct
4 Correct 682 ms 24544 KB Output is correct
5 Correct 569 ms 21484 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 12808 KB Output is correct
2 Correct 743 ms 12808 KB Output is correct
3 Correct 716 ms 12868 KB Output is correct
4 Correct 779 ms 12808 KB Output is correct
5 Correct 639 ms 23956 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 12808 KB Output is correct
2 Correct 748 ms 12748 KB Output is correct
3 Correct 610 ms 22344 KB Output is correct
4 Correct 779 ms 28404 KB Output is correct
5 Correct 649 ms 24360 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 15948 KB Output is correct
2 Correct 932 ms 15948 KB Output is correct
3 Correct 898 ms 15952 KB Output is correct
4 Correct 974 ms 15948 KB Output is correct
5 Correct 773 ms 29508 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 980 ms 15948 KB Output is correct
2 Correct 929 ms 15948 KB Output is correct
3 Correct 774 ms 28228 KB Output is correct
4 Correct 971 ms 35428 KB Output is correct
5 Correct 811 ms 30652 KB Output is correct