oj.uz

Submission #1102817

# Submission time Handle Problem Language Result Execution time Memory
1102817 2024-10-19T03:40: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 - r.y * r.y);
                if (Double.isNaN(left)) continue;
                queue.add(Math.max(left, 0));
                queue.add(-Math.min(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 77 ms 13956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 903 ms 37060 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 1051 ms 39352 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 1072 ms 40148 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 1058 ms 39196 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 1064 ms 121780 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 1065 ms 120960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 108320 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 1063 ms 112868 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 1042 ms 114092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 841 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 Execution timed out 1014 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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