oj.uz

Submission #1102812

# Submission time Handle Problem Language Result Execution time Memory
1102812 2024-10-19T03:26:42 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));
            }

            if (queue.isEmpty()) 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 Range {
        public final int x, y;
        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 78 ms 13736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 350 ms 18352 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 1035 ms 34744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 958 ms 37128 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 1067 ms 39116 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 1064 ms 39740 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 1064 ms 39484 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 1051 ms 121700 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 1046 ms 120960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
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 -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 108576 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 1064 ms 112792 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 1034 ms 113864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 843 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 911 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 953 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 966 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -