oj.uz

Submission #1066701

# Submission time Handle Problem Language Result Execution time Memory
1066701 2024-08-20T05:06:27 Z Oz121 Balloons (CEOI11_bal) Java 11
100 / 100
 1702 ms 43408 KB 
import java.io.*;
import java.util.*;
public class bal {
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine()); int num = Integer.parseInt(l1.nextToken()); double[][] arr = new double[num][2];
        for (int i = 0;i<num;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> idx = new Stack<>(); double[] ans = new double[num];
        for (int i = 0;i<num;i++) {
            double newR = arr[i][1];
            while (!idx.isEmpty()) {
                int j = idx.peek();
                double maxR = Math.pow(arr[i][0]-arr[j][0],2)/(4*ans[j]);

                if (maxR>arr[i][1]) {
                    if (arr[i][1]<=ans[j]) {
                        idx.add(i); break;
                    }
                    else idx.pop();
                } else { //maxR<=arr[i][1]
                    newR = Math.min(newR, maxR);
                    if (newR<=ans[j]) {
                        idx.add(i);
                        break;
                    }
                    else idx.pop();
                }
            }

            ans[i] = newR;
            idx.add(i);
        }

        for (double i : ans) System.out.println(i+" ");
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 17120 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 20736 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1261 ms 35592 KB 50000 numbers
2 Correct 713 ms 19872 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1411 ms 36444 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1162 ms 32540 KB 115362 numbers
2 Correct 963 ms 26752 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 35024 KB 154271 numbers
2 Correct 1216 ms 42620 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 39748 KB 200000 numbers
2 Correct 1208 ms 43408 KB 199945 numbers