#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1000000000000000000LL;
ll n, m, q, k, x, y, a, c;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
n = r.size();
m = b.size();
set< pair<ll, pair<ll, ll> > > two, one;
vector<bool> used1(n), used2(m);
for (int i = 0; i < n; i++) {
if (r[i] <= b[b.size() - 1]) {
ll x = lower_bound(b.begin(), b.end(), r[i]) - b.begin();
two.insert({abs(r[i] - b[x]), {i, x}});
}
if (r[i] >= b[0]) {
ll x = (--upper_bound(b.begin(), b.end(), r[i])) - b.begin();
two.insert({abs(r[i] - b[x]), {i, x}});
}
}
for (int i = 0; i < m; i++) {
if (b[i] <= r[r.size() - 1]) {
ll x = lower_bound(r.begin(), r.end(), b[i]) - r.begin();
two.insert({abs(r[x] - b[i]), {x, i}});
}
if (b[i] >= r[0]) {
ll x = (--upper_bound(r.begin(), r.end(), b[i])) - r.begin();
two.insert({abs(r[x] - b[i]), {x, i}});
}
}
// for (auto i : two) {
// cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n';
// }
// cout << '\n';
ll ans = 0;
while (two.size() > 0 || one.size() > 0) {
pair<ll, ll> p1 = {-1, -1}, p2 = {-1, -1};
while (!two.empty() && p2.first == -1) {
p2 = (*two.begin()).second;
two.erase({abs(r[p2.first] - b[p2.second]), p2});
if (used1[p2.first] && used2[p2.second]) {
p2 = {-1, -1};
continue;
}
if (used1[p2.first] || used2[p2.second]) {
one.insert({abs(r[p2.first] - b[p2.second]), p2});
p2 = {-1, -1};
continue;
}
break;
}
while (!one.empty() && p1.first == -1) {
p1 = (*one.begin()).second;
one.erase({abs(r[p1.first] - b[p1.second]), p1});
if (used1[p1.first] && used2[p1.second]) {
p1 = {-1, -1};
continue;
}
break;
}
if (p1.first == -1 && p2.first == -1) {
break;
}
// cout << p1.first << ' ' << p1.second << '\n';
// cout << p2.first << ' ' << p2.second << '\n';
// for (auto i : used1) {
// cout << i << ' ';
// }
// cout << '\n';
// for (auto i : used2) {
// cout << i << ' ';
// }
// cout << '\n';
// cout << '\n';
ll a1 = (p1.first == -1 ? INF : abs(r[p1.first] - b[p1.second]));
a1 *= 2;
ll a2 = (p2.first == -1 ? INF : abs(r[p2.first] - b[p2.second]));
if (a2 < a1) {
ans += a2;
used1[p2.first] = 1;
used2[p2.second] = 1;
}
else {
ans += a1 / 2;
used1[p1.first] = 1;
used2[p1.second] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '41977' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '904', found: '946' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '316', found: '356' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '27', found: '29' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '41977' |
| 2 |
Halted |
0 ms |
0 KB |
- |
