Submission #1269816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269816		kduckp	Balloons (CEOI11_bal)	C++20	100 / 100	102 ms	6496 KiB

bal

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define EYMK signed main()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define each(x) for(auto & i : x)
#define vvi vector<vi>
#define pb push_back
#define endl '\n'
#define yesno(x) cout << ((x) ? "YES\n" : "NO\n")
#define debug(x) cerr << #x << " = " << (x) << endl
#define debug2(x, y) cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define debug3(x, y, z) cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl
const int MOD = 1e9 + 7;
const int LARGEPRIME = 998244353;
const int INF_INT = 2147483647;
const ll INF_LL = 2 * 1e18;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dx8[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy8[] = {0, 0, -1, 1, -1, 1, -1, 1};

int n;
pair<double, double> a[200005];
double max_rad[200005];

double calc(pair<double, double> balloon, double current_x)
{
    double dx = balloon.fi - current_x;
    return (dx * dx) / (4.0 * balloon.se);
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se; // first la toa do truc tung, second la ban kinh toi da
    }

    deque<pair<double, double>> dq;
    max_rad[1] = a[1].se;
    dq.pb({a[1].fi, max_rad[1]});

    for(int i = 2; i <= n; i++)
    {
        double cur_x = a[i].fi;
        double cur_r = a[i].se;
        double max_r = cur_r;

        while(!dq.empty())
        {
            double possible_r = calc(dq.back(), cur_x);
            max_r = min(max_r, possible_r);

            if(max_r >= dq.back().se)
            {
                dq.pop_back();
            }
            else break;
        }

        max_rad[i] = max_r;
        dq.pb({cur_x, max_r});
    }

    cout << fixed << setprecision(3);
    for(int i = 1; i <= n; i++)
    {
        cout << max_rad[i] << endl;
    }
}

EYMK
{
    fast;
    if (fopen("bal.inp", "r")) {
        freopen("bal.inp", "r", stdin);
        freopen("bal.out", "w", stdout);
    }
    solve();
    return 0;
}

Compilation message (stderr)

bal.cpp: In function 'int main()':
bal.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen("bal.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bal.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("bal.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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