oj.uz

Submission #1102805

# Submission time Handle Problem Language Result Execution time Memory
1102805 2024-10-19T02:30:35 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]);

        Range[] ranges = new Range[n];
        for (int i = 0; i < n; i++) {
            first = reader.readLine().split(" ");
            ranges[i] = new Range(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 (Range 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));
            }

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

                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 Range {
        public final int x, y;
        public double left, right;
        public Range(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 15348 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 17832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 828 ms 38232 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 42212 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 1065 ms 43776 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 1072 ms 44044 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 1050 ms 99160 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 1071 ms 103688 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 1052 ms 117272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
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 #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 847 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 653 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 669 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 687 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -