oj.uz

Submission #605317

# Submission time Handle Problem Language Result Execution time Memory
605317 2022-07-25T15:32:47 Z chuangsheep Balloons (CEOI11_bal) C++11
100 / 100
 335 ms 3344 KB 
#include <bits/stdc++.h>
using namespace std;

/*
 * how long can the radius of the new balloon at position bx be
 * so that it touches the ballon a, which is described by
 * its x position a.first and its radius a.second
 */
double calc_r(pair<double, double> a, double bx) {
  return (a.first - bx) * (a.first - bx) / (4 * a.second);
}

int main() {
  // number of balloons
  int n;
  cin >> n;

  // the radius of each balloon after inflating
  vector<double> res(n);
  // the balloons we should check when we add a new one
  stack<pair<double, double>> to_check;

  // simulate inflating balloons
  for (int i = 0; i < n; i++) {
    /*
     * the x coordinate and the maximum radius of the
     * current balloon being inflated
     */
    double x, r;
    cin >> x >> r;

    // the maximum radius of the current balloon
    double max_r = r;
    /*
     * as long as the stack is not empty, we want to check
     * if the last balloon makes the radius of the current balloon smaller
     */
    while (!to_check.empty()) {
      pair<double, double> last = to_check.top();
      // the radius if the current balloon touches the last balloon
      double to_last_r = calc_r(last, x);
      /*
       * the maximum possible radius is the smaller one between current
       * maximum and the maximum radius so that we touches the last balloon
       * (by which we have to stop)
       */
      max_r = min(max_r, to_last_r);

      /*
       * if current maximum radius >= radius of the last balloon, we can
       * remove the last balloon since it will never be touched by any
       * new balloons other than the current one
       */
      if (max_r >= last.second) {
        to_check.pop();
        // check the next balloon saved which will possibly reduce max_r
        continue;
      }
      /*
       * otherwise, the current balloon is smaller than the last saved balloon
       * and we can stop checking
       */
      else {
        break;
      }
    }
    /*
     * save the x coordinate and radius of the current balloon, so that
     * it can be checked later when a new balloon being inflated
     */
    to_check.push({x, max_r});

    res[i] = max_r;
  }

  cout << fixed << setprecision(3);
  for (double &r : res) {
    cout << r << "\n";
  }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 612 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1264 KB 50000 numbers
2 Correct 89 ms 956 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 1996 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 2264 KB 115362 numbers
2 Correct 188 ms 1900 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 2888 KB 154271 numbers
2 Correct 324 ms 3032 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 3344 KB 200000 numbers
2 Correct 335 ms 3160 KB 199945 numbers