Submission #407310

#	Time	Username	Problem	Language	Result	Execution time	Memory
407310		phisti	Mobile (BOI12_mobile)	C++17	0 / 100	1093 ms	63828 KiB

mobile

// 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 (stderr)

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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5