oj.uz

Submission #869272

# Submission time Handle Problem Language Result Execution time Memory
869272 2023-11-03T23:27:05 Z tvladm2009 Balloons (CEOI11_bal) C++17
100 / 100
 176 ms 13248 KB 
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;
typedef long double ld;
const int N = (int)2e5 + 7;
ld x[N], r[N];
int n;

struct Circle {
        ld x;
        ld y;
        ld radius;
};

bool check(Circle a, Circle b) {
        if (4 * a.x * b.x >= (a.y - b.y) * (a.y - b.y)) {
                return false;
        }
        return true;
}

int main() {
#ifndef ONPC
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#else
        FILE* stream;
        freopen("input.txt", "r", stdin);
#endif
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> x[i] >> r[i];
        }
        vector<pair<ld, ld>> stk;
        for (int i = 1; i <= n; i++) {
                ld cur = r[i];
                while (!stk.empty()) {
                        ld dist = x[i] - stk.back().second;
                        cur = min(cur, dist * dist / (4 * stk.back().first));
                        if (stk.back().first <= cur) {
                                stk.pop_back();
                        }
                        else {
                                break;
                        }
                }
                cout << setprecision(10) << fixed << cur << "\n";
                stk.push_back({cur, x[i]});
        }
        return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5212 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6356 KB 50000 numbers
2 Correct 40 ms 6480 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7892 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 8652 KB 115362 numbers
2 Correct 104 ms 9300 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 10200 KB 154271 numbers
2 Correct 162 ms 13248 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 11360 KB 200000 numbers
2 Correct 158 ms 13164 KB 199945 numbers