oj.uz

Submission #571357

# Submission time Handle Problem Language Result Execution time Memory
571357 2022-06-01T22:32:50 Z DylanSmith Balloons (CEOI11_bal) Java 11
100 / 100
 1998 ms 34596 KB 
import java.util.*;
import java.io.*;
public class bal {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt();
        int[] x = new int[N];
        double[] r = new double[N];
        for (int i = 0; i < N; i++) {
            x[i] = in.nextInt();
            r[i] = in.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && r[stack.peek()] <= r[i]) {
                if (Math.pow(x[i] - x[stack.peek()], 2) / (4.0 * r[stack.peek()]) < r[i]) {
                    r[i] = Math.pow(x[i] - x[stack.peek()], 2) / (4.0 * r[stack.peek()]);
                }
                if (r[stack.peek()] <= r[i]) {
                    stack.pop();
                }
            }
            if (!stack.isEmpty() && Math.pow(x[i] - x[stack.peek()], 2) / (4.0 * r[stack.peek()]) < r[i]) {
                r[i] = Math.pow(x[i] - x[stack.peek()], 2) / (4.0 * r[stack.peek()]);
            }
            stack.push(i);
        }
        for (int i = 0; i < N; i++) {
            out.printf("%.3f%n", r[i]);
        }
        
        out.close();
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9648 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 9220 KB 2 numbers

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 17712 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 25952 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1902 ms 34596 KB 50000 numbers
2 Correct 1032 ms 26928 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1998 ms 34324 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1535 ms 30492 KB 115362 numbers
2 Correct 1127 ms 29664 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1705 ms 31864 KB 154271 numbers
2 Correct 1174 ms 32780 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1969 ms 34156 KB 200000 numbers
2 Correct 1197 ms 32888 KB 199945 numbers