Submission #1120013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120013		jobseeker	Balloons (CEOI11_bal)	C++17	100 / 100	140 ms	10352 KiB

bal

#include "assert.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

// #include <math.h>
// #include <bits/stdc++.h>
// clang-format off
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T>
// using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// //map
// tree <int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> m;
// //multiset
// tree <pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> s;
// s.find_by_order();
// s.order_of_key(); //#strictly smaller.

template <typename T> ostream& operator<<(ostream& out, const vector<T>& vec) {
    if (vec.empty()) { out << "{}"; return out; } out << '{';
    for (int i = 0; i < vec.size() - 1; i++) { out << vec[i] << ", "; }
    return out << vec.back() << '}'; }
template <typename T, size_t N> ostream& operator<<(ostream& out, const array<T, N>& vec) {
    if (vec.empty()) { out << "{}"; return out; } out << '{';
    for (int i = 0; i < vec.size() - 1; i++) { out << vec[i] << ", "; }
    return out << vec.back() << '}'; }
template <typename T> ostream& operator<<(ostream& out, const set<T>& set) {
    out << '{'; for (auto it = set.begin(); it != set.end(); it++) { 
        T element = *it; out << element; if (std::next(it) != set.end()) {out << ", ";} }
    return out << '}'; }
template <typename T> istream &operator>>(istream &in, vector<T> &a) {
    for (int i = 0; i < a.size(); ++i) {
        in >> a[i];
    } return in; }
template <typename T, size_t N> istream &operator>>(istream &in, array<T, N> &a) {
    for (int i = 0; i < N; ++i) {
        in >> a[i];
    } return in; }
template <typename T> T min(vector<T> &a) {
    T ans = a[0];
    for (int i = 1; i < a.size(); ++i) { if (a[i] < ans) { ans = a[i]; } } return ans; }
template <typename T> T max(vector<T> &a) {
    T ans = a[0];
    for (int i = 1; i < a.size(); ++i) { if (a[i] > ans) { ans = a[i]; } } return ans; }
    
#define FOR3(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define FOR2(i, a) for (int i=0; i<(signed)(a); i++)
#define GET_MACRO2(_1,_2,_3,NAME,...) NAME
#define FOR(...) GET_MACRO2(__VA_ARGS__, FOR3, FOR2)(__VA_ARGS__)
#define RFOR(i, b, a) for (int i=(b); i>=(signed)(a); i--)

#define dbg1(v) cerr << "L" << __LINE__ << "> " << #v << "=" << (v) << endl;
#define dbg2(x,y) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << endl;
#define dbg3(x,y,z) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << ", " << #z << "=" << (z) << endl;
#define dbg4(x,y,z,w) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << ", " << #z << "=" << (z) << ", " << #w << "=" << (w) << endl;
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define dbg(...) GET_MACRO(__VA_ARGS__, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#define ll long long
#define ar array
#define nl "\n"
using vi = vector<int>;
using vll = vector<ll>;
using ii = ar<int, 2>;
// clang-format on

// #ifdef LOCAL
// #include "algo/debug.h"
// #else
// #define debug(...) 42
// #endif

const int M = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const char dir[4] = {'U', 'R', 'D', 'L'};
const double eps = 1e-9;

auto xdiv = [](const ar<double, 2> &v1, const ar<double, 2> &v2) {
    double x1 = v1[0], x2 = v2[0];
    double r1 = v1[1], r2 = v2[1];
    double z1 = 1 / sqrt(r1), z2 = 1 / sqrt(r2);
    double y1 = x1 * z1, y2 = x2 * z2;
    return (y2 - y1) / (z2 - z1);
};

vector<double> solve1(int n, vector<ar<double, 2>> &a) {
    vector<ar<double, 2>> s; // x, r
    vector<double> ans;
    FOR(i, n) {
        double x = a[i][0], r = a[i][1];
        // cin >> x >> r;
        if (s.size()) {
            while (s.size() > 1 && x >= xdiv(*(s.rbegin() + 1), s.back())) {
                s.pop_back();
            }
            double d = x - s.back()[0];
            chmin(r, d * d / 4 / s.back()[1]);
            while (s.size() > 0 && r >= s.back()[1] || s.size() > 1 && xdiv(*(s.rbegin() + 1), s.back()) <= xdiv(s.back(), {x, r})) {
                s.pop_back();
            }
        }
        s.push_back({x, r});
        ans.push_back(r);
    }
    return ans;
}

vector<double> solve2(int n, vector<ar<double, 2>> &a) {
    vector<double> ans(n);
    FOR(i, n) {
        double x = a[i][0], r = a[i][1];
        FOR(j, 0, i - 1) {
            double d = x - a[j][0];
            chmin(r, d * d / 4 / ans[j]);
        }
        ans[i] = r;
    }
    return ans;
}
int main() {
#ifndef __APPLE__
    // freopen("exercise.in", "r", stdin);
    // freopen("exercise.out", "w", stdout);
#endif
    //	ifstream in("/Users/a/Downloads/test_input.txt");
    //	cin.rdbuf(in.rdbuf());
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<ar<double, 2>> a(n);
    FOR(i, n) {
        cin >> a[i][0] >> a[i][1];
    }
    auto ans = solve1(n, a);
    FOR(i, n) {
        cout << fixed << setprecision(3) << ans[i] << nl;
    }

    // random_device rd;
    // mt19937 generator(rd());
    // // uniform_int_distribution<int> dist(1, 100); // including both ends
    // uniform_real_distribution<double> dist(1.0, 1000.0);
    // FOR(T, 10000) {
    //     int n = 400;
    //     vector<ar<double, 2>> a(n);
    //     FOR(i, n) {
    //         a[i][0] = dist(generator);
    //         a[i][1] = 1e9;
    //     }
    //     sort(a.begin(), a.end());
    //     a[0][1] = 10;
    //     auto ans1 = solve1(n, a);
    //     auto ans2 = solve2(n, a);
    //     bool eq = true;
    //     FOR(i, n) {
    //         if (abs(ans1[i] - ans2[i]) > 1e-6) {
    //             eq = false;
    //             break;
    //         }
    //     }
    //     if (!eq) {
    //         dbg(T);
    //         dbg(a);
    //         dbg(ans1);
    //         dbg(ans2);
    //         break;
    //     }
    // }
}

Compilation message (stderr)

bal.cpp: In function 'std::vector<double> solve1(int, std::vector<std::array<double, 2> >&)':
bal.cpp:121:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  121 |             while (s.size() > 0 && r >= s.back()[1] || s.size() > 1 && xdiv(*(s.rbegin() + 1), s.back()) <= xdiv(s.back(), {x, r})) {

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10