oj.uz

Submission #1046835

# Submission time Handle Problem Language Result Execution time Memory
1046835 2024-08-07T04:32:10 Z JohnnyVenturas Mobile (BOI12_mobile) C++17
8 / 100
 474 ms 24656 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

pair<int, int> receivers[MAXN];

int last_true(int low, int high, function<bool(double)> f) {
  --low;

  for (int diff = high - low; diff > 0; diff /= 2) {
    while (low + diff <= high && f(low + diff))
      low += diff;
  }

  return low;
}

double first_true(double low, double high, function<bool(double)> f) {
  --low, ++high;

  double mid;

  while (high - low > 1e-3) {
    mid = low + (high - low) / 2;
    if (f(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }

  return high;
}

bool intersect(pair<int, int> &center, double r, double L, double &left,
               double &right) {
  const auto &[x, y] = center;

  double c = y;
  double y0 = -c;
  double d0 = abs(c);

  left = -1 / 0., right = -1 / 0.;

  if (d0 > r)
    return false;

  double d = sqrt(r * r - d0 * d0);

  double m = d;

  double ax = m, ay = y0;
  double bx = -m, by = y0;

  left = ax + x;
  right = bx + x;
  if(left > right) swap(left, right);

  return true;
}

int main() {
  int N, L;
  cin >> N >> L;

  for (int i = 0; i < N; ++i) {
    cin >> receivers[i].first >> receivers[i].second;
  }


  cout << first_true(0.001, 1e9, [&](double r) {
	 double last_right = 0.0;
    for (int i = 0; i < N; ++i) {
      double left, right;
      bool did_intersect = intersect(receivers[i], r, L, left, right);

	  if(!did_intersect) continue;

	  if(right < 0) continue;

	  if(left > last_right) continue;

	  last_right = max(last_right, right);
    }

	return last_right >= L;

  }) << "\n";
}

Compilation message

mobile.cpp: In function 'bool intersect(std::pair<int, int>&, double, double, double&, double&)':
mobile.cpp:54:18: warning: unused variable 'ay' [-Wunused-variable]
   54 |   double ax = m, ay = y0;
      |                  ^~
mobile.cpp:55:19: warning: unused variable 'by' [-Wunused-variable]
   55 |   double bx = -m, by = y0;
      |                   ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 2 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3420 KB Output is correct
2 Incorrect 31 ms 3676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3164 KB Output is correct
2 Correct 24 ms 3708 KB Output is correct
3 Incorrect 28 ms 3676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3164 KB Output is correct
2 Incorrect 35 ms 3788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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