oj.uz

Submission #1046843

# Submission time Handle Problem Language Result Execution time Memory
1046843 2024-08-07T04:46:49 Z JohnnyVenturas Mobile (BOI12_mobile) C++17
8 / 100
 568 ms 8036 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(long double)> f) {
  --low;

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

  return low;
}

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

  long 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, long double r, long double L, long double &left,
               long double &right) {
  const auto &[x, y] = center;

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

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

  if (d0 > r)
    return false;

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

  long double m = d;

  long double ax = m, ay = y0;
  long 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.0001, 2e9, [&](long double r) {
	 long double last_right = 0.0;
    for (int i = 0; i < N; ++i) {
      long double left, right;
      bool did_intersect = intersect(receivers[i], r, L, left, right);

	  if(!did_intersect) continue;

	  if(right + 1e-3 < 0) continue;

	  if(left > last_right + 1e-3) continue;

	  last_right = max(last_right, right);
    }

	return last_right >= L;

  }) << "\n";
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 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 3 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 348 KB Output is correct
2 Incorrect 3 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 3 ms 344 KB Output is correct
2 Incorrect 3 ms 444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2652 KB Output is correct
2 Correct 29 ms 2668 KB Output is correct
3 Incorrect 34 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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