oj.uz

답안 #754176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754176 2023-06-07T06:12:31 Z lukehsiao Mobile (BOI12_mobile) C++14
8 / 100
 1000 ms 32344 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 1e6;
ll n, L, x[mxN], y[mxN];

struct Range {
	double lo, hi;
	Range(double l, double r) : lo(l), hi(r) {};
	bool operator<(const Range &r) const {
		return hi < r.lo;
	}
	void merge(const Range &r) {
		lo = min(lo, r.lo);
		hi = max(hi, r.hi);
	}
};

bool works(double r) {
	set<Range> s;
	for (int i=0; i<n; ++i) {
		double d = r*r - y[i]*y[i];
		if (d >= 0) {
			Range rng = Range(x[i]-sqrt(d), x[i]+sqrt(d));
			auto it1 = s.lower_bound(rng);
			auto it2 = s.upper_bound(rng);
			while (it1 != it2) {
				rng.merge(*it1);
				it1 = s.erase(it1);
			}
			s.insert(rng);
		}
	}
	for (const Range &rng : s)
		if (rng.lo <= 0 && rng.hi >= L)
			return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> L;
	for (int i=0; i<n; ++i)
		cin >> x[i] >> y[i];
	
	double lo = 0, hi = 3e9;
	while (hi-lo > 1e-3) {
		double mid = (lo+hi)/2;
		if (works(mid))
			hi = mid;
		else
			lo = mid;
	}

	cout << (lo+hi)/2 << '\n';
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 5 ms 400 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Incorrect 5 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 456 KB Output is correct
2 Incorrect 9 ms 472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 340 KB Output is correct
2 Incorrect 9 ms 464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 468 KB Output is correct
2 Incorrect 9 ms 412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 2380 KB Output is correct
2 Incorrect 139 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 2292 KB Output is correct
2 Correct 63 ms 2120 KB Output is correct
3 Incorrect 81 ms 2516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 2324 KB Output is correct
2 Incorrect 137 ms 2768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 172 ms 3432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 196 ms 3580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 871 ms 12432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 885 ms 16336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1025 ms 14956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1051 ms 19656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1058 ms 17312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1059 ms 22768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1050 ms 19744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1055 ms 25956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1061 ms 24608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1071 ms 32344 KB Time limit exceeded
2 Halted 0 ms 0 KB -