oj.uz

Submission #684711

# Submission time Handle Problem Language Result Execution time Memory
684711 2023-01-22T11:07:44 Z nayhz Mobile (BOI12_mobile) C++17
100 / 100
 346 ms 15956 KB 
// source identifier task_name
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#define lck cout << "ick bmi 32.9\n"
#define cam_cs cout << "ick orz\n"
#define orz(x) cout << (x) << " orz\n"

#define pii pair<int, int>
#define pll pair<long long, long long>
#define pcc pair<char, char>
#define ll long long
#define ull unsigned long long
#define ld long double
#define int long long

#define vi vector<int>
#define vll vector<long long>
#define vd vector<double>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long, long long>>
#define vc vector<char>
#define vsc vector<string>
#define vb vector<bool>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define yes() cout << "Yes\n"
#define no() cout << "No\n"
#define impossible() cout << "Impossible\n"

template<typename T, typename V>
inline void print (const std::pair<T, V> &x) {std::cout << x.first << ' ' << x.second << '\n';}
template<typename T>
inline void print (const T &x) {std::cout << x << '\n';}
template<typename T>
inline void print (std::vector<T> &x) {for (auto &y : x) std::cout << y << " "; std::cout << '\n';}
inline void print () {std::cout << '\n';}
using namespace std;

const ld pi = acos(-1);
const ld eps = 1e-9;
const ll mod = 1000000007;
const ll inf = 1000000007;

clock_t T, NT;
inline double get_time() {NT = clock() - T; return (double)(NT) / CLOCKS_PER_SEC;}

void file_io (string x);

/*
>>>>>>>>>>>>>>>>>>>>>>>>>>END OF TEMPLATE HEADER<<<<<<<<<<<<<<<<<<<<<<<<
*/

void solve (/*int &tc*/) {
	int n, len; cin >> n >> len;
	vpii a(n);
	for (auto &x : a) cin >> x.fi >> x.se;

	double l = 1, r = 1.5e9, mid;
	double curr, temp, lb, rb;
	while (r - l > 1e-3) {
		mid = (l + r) / 2;
		curr = 0;

		for (int i = 0; i < n; i++) {
			temp = sqrt(mid * mid - a[i].se * a[i].se);
			lb = a[i].fi - temp, rb = a[i].fi + temp;

			if (lb <= curr) curr = max(curr, rb);
			if (curr >= len) break;
		}
		if (curr >= len) r = mid;
		else l = mid;
	}
	cout << fixed << setprecision(4) << l << '\n';
}

signed main () {
	cin.tie(0)->sync_with_stdio(false);
	T = clock();
	srand(time(NULL));
	// file_io("");

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(/*i*/);
		// if (i != t) cout << '\n';
	}
	// while (true) {solve(t); t++;}
	return 0;
}

// void file_io (string x = "x") {
// 	string i = x + ".in";
// 	freopen(i.c_str(), "r", stdin);
// 	string o = x + ".out";
// 	freopen(o.c_str(), "w", stdout);
// }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 316 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory 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 1 ms 316 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 2 ms 468 KB Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2260 KB Output is correct
2 Correct 19 ms 2128 KB Output is correct
3 Correct 11 ms 1748 KB Output is correct
4 Correct 28 ms 2008 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2260 KB Output is correct
2 Correct 19 ms 2004 KB Output is correct
3 Correct 25 ms 2140 KB Output is correct
4 Correct 24 ms 2124 KB Output is correct
5 Correct 34 ms 2312 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2376 KB Output is correct
2 Correct 20 ms 2552 KB Output is correct
3 Correct 21 ms 2508 KB Output is correct
4 Correct 36 ms 2768 KB Output is correct
5 Correct 22 ms 2260 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2772 KB Output is correct
2 Correct 22 ms 2772 KB Output is correct
3 Correct 22 ms 2668 KB Output is correct
4 Correct 36 ms 2760 KB Output is correct
5 Correct 29 ms 2492 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2748 KB Output is correct
2 Correct 24 ms 2776 KB Output is correct
3 Correct 20 ms 2772 KB Output is correct
4 Correct 36 ms 2892 KB Output is correct
5 Correct 27 ms 2448 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10060 KB Output is correct
2 Correct 127 ms 11176 KB Output is correct
3 Correct 110 ms 11324 KB Output is correct
4 Correct 177 ms 11340 KB Output is correct
5 Correct 137 ms 9592 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10784 KB Output is correct
2 Correct 192 ms 10032 KB Output is correct
3 Correct 105 ms 9352 KB Output is correct
4 Correct 168 ms 9940 KB Output is correct
5 Correct 148 ms 9960 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 11452 KB Output is correct
2 Correct 141 ms 12524 KB Output is correct
3 Correct 132 ms 12440 KB Output is correct
4 Correct 226 ms 12468 KB Output is correct
5 Correct 167 ms 11664 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12548 KB Output is correct
2 Correct 234 ms 11592 KB Output is correct
3 Correct 123 ms 11384 KB Output is correct
4 Correct 212 ms 11656 KB Output is correct
5 Correct 178 ms 11468 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 12844 KB Output is correct
2 Correct 159 ms 13628 KB Output is correct
3 Correct 143 ms 13872 KB Output is correct
4 Correct 250 ms 13912 KB Output is correct
5 Correct 186 ms 12592 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 13468 KB Output is correct
2 Correct 255 ms 13320 KB Output is correct
3 Correct 151 ms 12532 KB Output is correct
4 Correct 238 ms 12208 KB Output is correct
5 Correct 193 ms 11960 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 13836 KB Output is correct
2 Correct 177 ms 13504 KB Output is correct
3 Correct 180 ms 13436 KB Output is correct
4 Correct 282 ms 13312 KB Output is correct
5 Correct 221 ms 12756 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 12844 KB Output is correct
2 Correct 274 ms 12756 KB Output is correct
3 Correct 161 ms 12756 KB Output is correct
4 Correct 274 ms 12756 KB Output is correct
5 Correct 226 ms 12756 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 15872 KB Output is correct
2 Correct 201 ms 15904 KB Output is correct
3 Correct 222 ms 15956 KB Output is correct
4 Correct 343 ms 15912 KB Output is correct
5 Correct 277 ms 15956 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 15956 KB Output is correct
2 Correct 346 ms 15956 KB Output is correct
3 Correct 204 ms 15956 KB Output is correct
4 Correct 341 ms 15956 KB Output is correct
5 Correct 281 ms 15956 KB Output is correct