이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
if (p1.first == n - 1 && p2.first == 0 && n > 1 && m > 1) {
continue;
}
// 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 |
---|
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |