oj.uz

Submission #1102820

# Submission time Handle Problem Language Result Execution time Memory
1102820 2024-10-19T03:44:53 Z uranium235 Mobile (BOI12_mobile) Java 11
0 / 100
 1000 ms 131072 KB 
//package ojuz;

import java.io.*;
import java.util.*;
import java.util.function.DoublePredicate;

public class mobile {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), l = Integer.parseInt(first[1]);

        Point[] ranges = new Point[n];
        for (int i = 0; i < n; i++) {
            first = reader.readLine().split(" ");
            ranges[i] = new Point(Integer.parseInt(first[0]), Integer.parseInt(first[1]));
        }

        double radius = firstTrue(1e-9, 1e10, d -> {
//            System.out.println("testing " + d);
            Queue<Double> queue = new PriorityQueue<>((a, b) -> {
                if (Math.abs(a) != Math.abs(b)) return Double.compare(Math.abs(a), Math.abs(b));
                return Double.compare(b, a);
            });
            for (Point r : ranges) {
                double left = r.x - Math.sqrt(d * d - (double) r.y * r.y);
                if (Double.isNaN(left)) continue;
                queue.add(Math.max(left, 0));
                queue.add(-Math.min((double) r.x + r.x - left, l));
//                System.out.println("added " + (r.x + r.x - left));
            }

            if (queue.isEmpty() || queue.peek() != 0) return false;

            int in = 0;
            while (!queue.isEmpty()) {
                double val = queue.poll();
//                System.out.println("val " + val);
                if (val == -l) return true;

                if (val < 0) {
                    in--;
                    if (in == 0) return false;
                } else in++;
            }

            return true;
        });

        System.out.println(radius);
    }

    public static double firstTrue(double lo, double hi, DoublePredicate pred) {
        hi += Math.ulp(hi);
        double prevMid = -1;
        while (lo < hi) {
            double mid = lo + (hi - lo) / 2;
            if (Math.abs(mid - prevMid) < 1e-6) return lo;
            if (pred.test(mid)) hi = mid;
            else lo = mid + Math.ulp(mid);

            prevMid = mid;
        }
        return lo;
    }

    static class Point {
        public final int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 14240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 15640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 17760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 18168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 282 ms 18728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 18344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 992 ms 34656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 906 ms 37152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 998 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 863 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 908 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 980 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 961 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -