Submission #1198260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198260		aykhn	Balloons (CEOI11_bal)	C++20	60 / 100	265 ms	8452 KiB

bal

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 3e3 + 5;
const int mod = 1e9 + 7;

int check(long double a, long double x, long double b, long double y)
{
  return (a + b) * (a + b) >= (a - b) * (a - b) + (x - y) * (x - y);
}
long double findr(long double x, long double b, long double y)
{
  long double l = 0, r = 1000000000;
  while (r - l > 0.000001)
  {
    long double mid = (l + r) / 2;
    if (check(mid, x, b, y)) r = mid - 0.000001;
    else l = mid;
  }
  return l;
}

void _()
{
  int n;
  cin >> n;
  long double x[n], r[n];
  for (int i = 0; i < n; i++) cin >> x[i] >> r[i];
  vector<array<long double, 2>> v;
  for (int i = 0; i < n; i++)
  {
    while (!v.empty())
    {
      r[i] = min(r[i], findr(x[i], v.back()[0], v.back()[1]));
      if (r[i] >= v.back()[0]) v.pop_back();
      else break;
    }
    v.push_back({r[i], x[i]});
  }
  cout.precision(3);
  for (int i = 0; i < n; i++) cout << fixed << r[i] << ' ';
  cout << '\n';
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

• 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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10