oj.uz

Submission #440218

# Submission time Handle Problem Language Result Execution time Memory
440218 2021-07-01T19:02:43 Z ImaginaryIQ Balloons (CEOI11_bal) Java 11
50 / 100
 2000 ms 33596 KB 
import java.io.*;
import java.util.*;


public class bal {
    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;

        // standard input
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // USACO-style file input
        public Kattio(String problemName) throws IOException {
            super(new FileWriter(problemName + ".out"));
            r = new BufferedReader(new FileReader(problemName + ".in"));
        }

        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }

        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }

    static int n;
    static pair [] arr;
    static double [] ans;
    static Stack<pair> stack = new Stack<>();

    public static void main(String[] args) throws IOException {
        Kattio io = new Kattio();
        n = io.nextInt();
        arr = new pair[n+1];
        ans = new double[n+1];

        arr[0] = new pair(0 , 0);
        for (int i = 1; i <= n; i++) {
            arr[i] = new pair(io.nextInt(), io.nextInt());
        }


        for (int i = 1; i <= n; i++) {
            pair minRad = arr[i];
            while((!stack.isEmpty())){
                    minRad.y = Math.min(minRad.y, calIntersect(minRad));
                    if(minRad.y >= stack.peek().y) {
                        stack.pop();
                    }else{
                        break;
                    }
            }
            ans[i] = minRad.y;
            stack.add(minRad);
        }


        for (int i = 1; i <= n; i++) {
            io.printf("%.3f", ans[i]);
            if(i == n)
                break;
            io.println();
        }
        io.close();
    }

    static double calIntersect(pair p1){
        return Math.pow(stack.peek().x - p1.x, 2) / (4 * stack.peek().y);
    }



    public static class pair {

        private final int x;
        private double y;

        public pair(final int x, final double y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(final Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof pair)) {
                return false;
            }

            final pair pair = (pair) o;

            if (x != pair.x) {
                return false;
            }
            if (y != pair.y) {
                return false;
            }

            return true;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + (int)y;
            return result;
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 9428 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 9476 KB 2 numbers

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 19228 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1751 ms 22548 KB 20000 numbers

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 29420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 30372 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 27652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 31176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 33596 KB Time limit exceeded
2 Halted 0 ms 0 KB -