oj.uz

Submission #684710

# Submission time Handle Problem Language Result Execution time Memory
684710 2023-01-22T11:06:26 Z nayhz Mobile (BOI12_mobile) C++17
100 / 100
 415 ms 19984 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 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 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 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 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 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 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 2 ms 468 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1504 KB Output is correct
2 Correct 19 ms 2540 KB Output is correct
3 Correct 12 ms 1740 KB Output is correct
4 Correct 31 ms 2640 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 1492 KB Output is correct
2 Correct 18 ms 2184 KB Output is correct
3 Correct 22 ms 2612 KB Output is correct
4 Correct 26 ms 2708 KB Output is correct
5 Correct 30 ms 3084 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1620 KB Output is correct
2 Correct 24 ms 1492 KB Output is correct
3 Correct 20 ms 1620 KB Output is correct
4 Correct 34 ms 1876 KB Output is correct
5 Correct 23 ms 2644 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1876 KB Output is correct
2 Correct 24 ms 1876 KB Output is correct
3 Correct 21 ms 1876 KB Output is correct
4 Correct 35 ms 1876 KB Output is correct
5 Correct 28 ms 3036 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1876 KB Output is correct
2 Correct 22 ms 1876 KB Output is correct
3 Correct 26 ms 1876 KB Output is correct
4 Correct 38 ms 1876 KB Output is correct
5 Correct 28 ms 3164 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 8148 KB Output is correct
2 Correct 120 ms 8060 KB Output is correct
3 Correct 107 ms 8148 KB Output is correct
4 Correct 177 ms 8148 KB Output is correct
5 Correct 145 ms 11816 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8148 KB Output is correct
2 Correct 181 ms 8148 KB Output is correct
3 Correct 106 ms 11028 KB Output is correct
4 Correct 179 ms 11836 KB Output is correct
5 Correct 148 ms 11776 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 9684 KB Output is correct
2 Correct 130 ms 9684 KB Output is correct
3 Correct 126 ms 9684 KB Output is correct
4 Correct 229 ms 9684 KB Output is correct
5 Correct 175 ms 12844 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 9684 KB Output is correct
2 Correct 229 ms 9708 KB Output is correct
3 Correct 148 ms 12944 KB Output is correct
4 Correct 250 ms 12576 KB Output is correct
5 Correct 202 ms 12632 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 11220 KB Output is correct
2 Correct 160 ms 11220 KB Output is correct
3 Correct 154 ms 11892 KB Output is correct
4 Correct 278 ms 11912 KB Output is correct
5 Correct 212 ms 14404 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 11876 KB Output is correct
2 Correct 264 ms 11856 KB Output is correct
3 Correct 174 ms 14264 KB Output is correct
4 Correct 284 ms 14380 KB Output is correct
5 Correct 204 ms 14560 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 14052 KB Output is correct
2 Correct 205 ms 14820 KB Output is correct
3 Correct 185 ms 14720 KB Output is correct
4 Correct 291 ms 14568 KB Output is correct
5 Correct 234 ms 16584 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 15460 KB Output is correct
2 Correct 305 ms 15564 KB Output is correct
3 Correct 183 ms 16820 KB Output is correct
4 Correct 320 ms 16892 KB Output is correct
5 Correct 236 ms 16716 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 19340 KB Output is correct
2 Correct 209 ms 19092 KB Output is correct
3 Correct 243 ms 18744 KB Output is correct
4 Correct 379 ms 16760 KB Output is correct
5 Correct 296 ms 19912 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 19660 KB Output is correct
2 Correct 415 ms 18972 KB Output is correct
3 Correct 215 ms 19984 KB Output is correct
4 Correct 360 ms 16716 KB Output is correct
5 Correct 314 ms 19860 KB Output is correct