oj.uz

Submission #824214

# Submission time Handle Problem Language Result Execution time Memory
824214 2023-08-13T18:34:17 Z powervic08 Balloons (CEOI11_bal) Java 11
100 / 100
 1521 ms 35516 KB 
import java.util.*;
import java.io.*;

public class bal {

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = Integer.parseInt(f.readLine());
        double[] rad = new double[n];
        Stack<Balloon> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(f.readLine());
            int x = Integer.parseInt(st.nextToken());
            double r = Double.parseDouble(st.nextToken());
            if (stack.isEmpty()) {
                rad[i] = r;
                stack.push(new Balloon(x, r));
                continue;
            }
            // c1 = (a, b) c2 = (c, d)
            // d = (c - a) ^ 2 / 4b
            double cur = -1;
            while (!stack.isEmpty()) {
                Balloon b = stack.peek();
                if (cur == -1) {
                    cur = Math.pow((x - b.pos), 2) / 4 / b.rad;
                }
                else {
                    cur = Math.min(cur, Math.pow((x - b.pos), 2) / 4 / b.rad);
                }
                cur = Math.min(cur, r);
                if (cur >= b.rad) {
                    stack.pop();
                }
                else {
                    break;
                }
            }
            rad[i] = cur;
            stack.push(new Balloon(x, cur));
        }
        for (double d : rad) {
            out.printf("%.3f%n", d);
        }
        out.close();
        f.close();
    }

    static class Balloon {
        double rad;
        int pos;

        public Balloon(int a, double b) {
            rad = b;
            pos = a;
        }
    }

}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 17764 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 25848 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1457 ms 35516 KB 50000 numbers
2 Correct 877 ms 27060 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1521 ms 34024 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 30108 KB 115362 numbers
2 Correct 932 ms 29416 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1346 ms 31096 KB 154271 numbers
2 Correct 1032 ms 31988 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1515 ms 33292 KB 200000 numbers
2 Correct 1006 ms 31988 KB 199945 numbers