Submission #571357

#	Time	Username	Problem	Language	Result	Execution time	Memory
571357		DylanSmith	Balloons (CEOI11_bal)	Java	100 / 100	1998 ms	34596 KiB

bal

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10