oj.uz

Submission #1046837

# Submission time Handle Problem Language Result Execution time Memory
1046837 2024-08-07T04:33:16 Z JohnnyVenturas Mobile (BOI12_mobile) C++17
8 / 100
 455 ms 8020 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-5) {
    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 0 ms 344 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 344 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 348 KB Output is correct
4 Incorrect 1 ms 344 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 448 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 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 344 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2652 KB Output is correct
2 Incorrect 33 ms 2648 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 2664 KB Output is correct
2 Correct 27 ms 2652 KB Output is correct
3 Incorrect 41 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 28 ms 2652 KB Output is correct
2 Incorrect 44 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 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 44 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 163 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 227 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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