Submission #930440

#	Time	Username	Problem	Language	Result	Execution time	Memory
930440		Karoot	Mobile (BOI12_mobile)	C++17	100 / 100	847 ms	50860 KiB

mobile

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

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