oj.uz

Submission #407310

# Submission time Handle Problem Language Result Execution time Memory
407310 2021-05-18T17:38:42 Z phisti Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 63828 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,
    vector<pair<double, si>>& in_outs,
    double power,
    sl length)
{
    ul idx = 0;
    double p2 = power*power;
    FORE(tower, towers) {
        if (power > tower.second) {
            auto val = sqrt(p2 - tower.second * tower.second);
            in_outs[idx++] = make_pair(max(tower.first - val, 0.0), 1);
            in_outs[idx++] = make_pair(min(tower.first + val, length * 1.0), -1);
        }
    }
    
    sort(in_outs.begin(), in_outs.begin() + idx);
    if (idx == 0 || in_outs[0].first > 0 || in_outs[idx - 1].first < length) { return false; }

    si sum = 0;
    sl i = 0;
    while(in_outs[i].first == 0) {
        sum+=in_outs[i++].second;
    }
    
    if (sum == 0) { return false; }
    
    while(i < idx && in_outs[i].first < length) {
        sum += in_outs[i].second;

        if (sum == 0 && i < idx - 1 && in_outs[i + 1].first > in_outs[i].first) {
            return false;
        }
        
        i++;
    }
    
    return true;
}

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

    return 0;
}

Compilation message

mobile.cpp: In function 'bool is_covered(std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<double, int> >&, double, sl)':
mobile.cpp:80:13: warning: comparison of integer expressions of different signedness: 'sl' {aka 'long long int'} and 'ul' {aka 'long long unsigned int'} [-Wsign-compare]
   80 |     while(i < idx && in_outs[i].first < length) {
      |           ~~^~~~~
mobile.cpp:83:27: warning: comparison of integer expressions of different signedness: 'sl' {aka 'long long int'} and 'ul' {aka 'long long unsigned int'} [-Wsign-compare]
   83 |         if (sum == 0 && i < idx - 1 && in_outs[i + 1].first > in_outs[i].first) {
      |                         ~~^~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 327 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 4576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 5180 KB Output is correct
2 Incorrect 461 ms 5188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 577 ms 6544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 513 ms 6496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 27972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 31960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 33616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 38212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 39180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 44816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 44868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 51164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 55856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 63828 KB Time limit exceeded
2 Halted 0 ms 0 KB -