oj.uz

Submission #1116636

# Submission time Handle Problem Language Result Execution time Memory
1116636 2024-11-22T02:59:30 Z JeffLegendPower Mobile (BOI12_mobile) C++17
100 / 100
 488 ms 32584 KB 
// https://oj.uz/problem/view/BOI12_mobile

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define plli pair<ll, int>
#define pll pair<ll, ll>
#define pii pair<int, int>
// Usage: FOR(i, 0, N) {...}
#define FOR(i, start, end) for(int i = start; i < end; i++)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

struct comp {
    bool operator() (const plli& a, const plli& b) const {
        return a < b;
    }
};

typedef tree<plli, null_type, comp, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;


// Segtree start
const int Nmax = 1e5;  // limit for array size
int N;  // array size
int t[2 * Nmax];

int oper(int a, int b) {
    return a + b;
}

void build() {  // build the tree
  for (int i = N - 1; i > 0; --i) t[i] = oper(t[i<<1], t[i<<1|1]);
}

void modify(int p, int value) {  // set value at position p
  for (t[p += N] = value; p > 1; p >>= 1) t[p>>1] = oper(t[p], t[p^1]);
}

int query(int l, int r) {  // on interval [l, r)
  int res = 0;
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = oper(res, t[l++]);
    if (r&1) res = oper(res, t[--r]);
  }
  return res;
}
// Segtree end

#define pdd pair<double, double>

double dist2(pdd a, pdd b) {
	return (a.first - b.first) * (a.first - b.first)
	+ (a.second - b.second) * (a.second - b.second);
}

int main() {
    // Comment out for interactive problems
    ios::sync_with_stdio(false);
	cin.tie(nullptr);

    int N;
	ll L;
	cin >> N >> L;
 
	pdd s[N];
	for (int i = 0; i < N; i++) cin >> s[i].first >> s[i].second;
 
	double low = 0, high = 1e12;
	while (high - low > 0.000001) {
		double mid = low + (high - low) / 2;
 
		double x = 0;
		for (int i = 0; i < N; i++) {
			if (dist2({x, 0}, {s[i]}) > mid*mid) continue;
 
			// let x = s[i].first, y = s[i].second;
			// d^2 + y^2 = r^2
			// d = sqrt(r^2 - y^2)
            // let x2 be the current position
            // x2 = x + d
 
			x = s[i].first + sqrt(mid*mid - s[i].second * s[i].second);
		}

 
		if (x >= L) high = mid;
		else low = mid;
	}
 
	cout << fixed << setprecision(10) << high;
}

Compilation message

mobile.cpp: In function 'void setIO(std::string)':
mobile.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2420 KB Output is correct
2 Correct 29 ms 2640 KB Output is correct
3 Correct 21 ms 1932 KB Output is correct
4 Correct 34 ms 2812 KB Output is correct
5 Correct 17 ms 1616 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2380 KB Output is correct
2 Correct 41 ms 1360 KB Output is correct
3 Correct 38 ms 2752 KB Output is correct
4 Correct 38 ms 2708 KB Output is correct
5 Correct 41 ms 3208 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2384 KB Output is correct
2 Correct 31 ms 2896 KB Output is correct
3 Correct 41 ms 2536 KB Output is correct
4 Correct 46 ms 3912 KB Output is correct
5 Correct 45 ms 2640 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3552 KB Output is correct
2 Correct 39 ms 3296 KB Output is correct
3 Correct 34 ms 3056 KB Output is correct
4 Correct 59 ms 1872 KB Output is correct
5 Correct 56 ms 3288 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3408 KB Output is correct
2 Correct 35 ms 3312 KB Output is correct
3 Correct 67 ms 2888 KB Output is correct
4 Correct 48 ms 3920 KB Output is correct
5 Correct 53 ms 3296 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 12492 KB Output is correct
2 Correct 191 ms 15952 KB Output is correct
3 Correct 169 ms 8272 KB Output is correct
4 Correct 217 ms 17620 KB Output is correct
5 Correct 226 ms 14552 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 16472 KB Output is correct
2 Correct 240 ms 14664 KB Output is correct
3 Correct 170 ms 13900 KB Output is correct
4 Correct 221 ms 17364 KB Output is correct
5 Correct 220 ms 15568 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 14956 KB Output is correct
2 Correct 198 ms 19016 KB Output is correct
3 Correct 195 ms 18412 KB Output is correct
4 Correct 244 ms 21616 KB Output is correct
5 Correct 269 ms 17736 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 19696 KB Output is correct
2 Correct 268 ms 17648 KB Output is correct
3 Correct 186 ms 16204 KB Output is correct
4 Correct 232 ms 9808 KB Output is correct
5 Correct 265 ms 18640 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 17428 KB Output is correct
2 Correct 235 ms 22156 KB Output is correct
3 Correct 234 ms 21320 KB Output is correct
4 Correct 304 ms 24904 KB Output is correct
5 Correct 352 ms 20436 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 22788 KB Output is correct
2 Correct 320 ms 20652 KB Output is correct
3 Correct 228 ms 18964 KB Output is correct
4 Correct 274 ms 11344 KB Output is correct
5 Correct 293 ms 21320 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 19784 KB Output is correct
2 Correct 263 ms 25132 KB Output is correct
3 Correct 274 ms 24536 KB Output is correct
4 Correct 366 ms 25160 KB Output is correct
5 Correct 360 ms 13136 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 26020 KB Output is correct
2 Correct 392 ms 23624 KB Output is correct
3 Correct 273 ms 22320 KB Output is correct
4 Correct 357 ms 28232 KB Output is correct
5 Correct 365 ms 24496 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 24648 KB Output is correct
2 Correct 360 ms 28140 KB Output is correct
3 Correct 341 ms 30544 KB Output is correct
4 Correct 431 ms 30480 KB Output is correct
5 Correct 488 ms 29804 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 32584 KB Output is correct
2 Correct 439 ms 15952 KB Output is correct
3 Correct 318 ms 28232 KB Output is correct
4 Correct 397 ms 30880 KB Output is correct
5 Correct 425 ms 30792 KB Output is correct