#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
const int mxn = 2e5 + 100;
int n, m, d;
vector<ll> v(mxn);
ld ans = 0;
pair<ld, pair<ld, ld>> calc(vector<pair<ld, ld>> cur, vector<ld> dist) {
// cout << cur.size() << endl;
// for (auto x : cur) cout << x.first << " " << x.second << endl;
// cout << endl;
if (cur.size() <= 1) return {cur[0].first, {cur[0].second, dist[0]}};
int mid = cur.size() / 2;
bool odd = (cur.size() % 2);
int r = mid + 1;
ld MX = 0;
if (odd) mid--;
if (!odd) {
mid--;
r--;
ld D = cur[r].first - cur[mid].second;
ld total = d - D;
dist[mid] += total / 2;
dist[r] += total / 2;
MX = max(MX, dist[mid]);
MX = max(MX, dist[r]);
ans = max(ans, dist[mid]);
ans = max(ans, dist[r]);
cur[mid].first -= total / 2;
cur[mid].second -= total / 2;
cur[r].first += total / 2;
cur[r].second += total / 2;
r++;
mid--;
}
// cout << "! " << mid << " " << r << endl;
for (int i = mid; i >= 0 && r < cur.size(); i--) {
ld D = cur[r].first - cur[r - 1].second;
ld total = d - D;
dist[r] += total;
MX = max(MX, dist[r]);
ans = max(ans, dist[r]);
cur[r].first += total;
cur[r].second += total;
D = cur[i + 1].first - cur[i].second;
total = d - D;
dist[i] += total;
MX = max(MX, dist[i]);
ans = max(ans, dist[i]);
cur[i].first -= total;
cur[i].second -= total;
r++;
}
// cout << cur[0].first << " " << cur[cur.size() - 1].second << " " << MX << endl;
return {cur[0].first, {cur[cur.size() - 1].second, MX}};
}
void solve(vector<pair<ld, ld>> cur, vector<ld> dist) {
if (cur.size() <= 1) return;
vector<pair<ld, ld>> groups;
vector<ld> mx;
int start = 0, sz = 1;
ld MX = dist[0];
bool good = 1;
for (int i = 0; i < cur.size() - 1; i++) {
if (abs(cur[i + 1].first - cur[i].second) < d) {
good = 0;
sz++;
MX = max(MX, dist[i]);
}
else {
groups.push_back({start, start + sz - 1});
mx.push_back(MX);
MX = dist[i + 1];
start = i + 1;
sz = 1;
}
}
if (good) return;
groups.push_back({start, start + sz - 1});
mx.push_back(MX);
vector<pair<ld, ld>> newC;
vector<ld> newD;
for (auto x : groups) {
vector<pair<ld, ld>> v;
vector<ld> D;
for (int i = x.first; i <= x.second; i++) v.push_back({cur[i]}), D.push_back(dist[i]);
pair<ld, pair<ld, ld>> get = calc(v, D);
newC.push_back({get.first, get.second.first});
newD.push_back(get.second.second);
}
solve(newC, newD);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> d;
v.resize(n);
vector<pair<ld, ld>> rn;
vector<ld> dist;
for (int i = 0; i < n; i++) {
cin >> v[i];
rn.push_back({v[i], v[i]});
dist.push_back(0);
}
for (int i = 0; i < m; i++) {
ll x;
cin >> x;
v.push_back(x);
rn.push_back({x, x});
sort(all(rn));
dist.push_back(0);
n++;
ans = 0;
solve(rn, dist);
cout << ans << " ";
}
}
Compilation message
Main.cpp: In function 'std::pair<long double, std::pair<long double, long double> > calc(std::vector<std::pair<long double, long double> >, std::vector<long double>)':
Main.cpp:45:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = mid; i >= 0 && r < cur.size(); i--) {
| ~~^~~~~~~~~~~~
Main.cpp: In function 'void solve(std::vector<std::pair<long double, long double> >, std::vector<long double>)':
Main.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < cur.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2664 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2664 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1537 ms |
3800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1537 ms |
3800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
