# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883125 | fanwen | Measures (CEOI22_measures) | C++17 | 279 ms | 4700 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define file(name) \
if(fopen(name".inp", "r")) \
freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
const int MAX = 2e5 + 5;
int n, m, D, a[MAX];
namespace sub1 {
long long calc(const vector <int> &a) {
auto check = [&] (long long val) -> bool {
long long last = 1e18;
for (int i = (int) a.size() - 1; i >= 0; --i) {
if(last + val < a[i]) return false;
last = min(last - D, a[i] + val - D);
}
return true;
};
long long l = -1, r = 1e18;
while(r - l > 1) {
long long mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid;
}
return r;
}
void solve() {
D <<= 1;
for (int i = 1; i <= n; ++i) a[i] <<= 1;
vector <int> b(a + 1, a + n + 1);
for (int i = 1; i <= m; ++i) {
int x; cin >> x;
b.push_back(x << 1);
sort(b.begin(), b.end());
long long ans = calc(b);
cout << ans / 2;
if(ans & 1) cout << ".5";
cout << " ";
}
exit(0);
}
}
void you_make_it(void) {
cin >> n >> m >> D;
for (int i = 1; i <= n; ++i) cin >> a[i];
if(n > 0) sub1::solve();
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
file("CEOI22_measures");
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |