| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1226174 | The_Samurai | Wiring (IOI17_wiring) | C++20 | 0 ms | 0 KiB |
#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;
ll solve(vector<int> a, vector<int> b, bool rev) {
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
int n = a.size(), m = b.size();
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
sort(v.begin(), v.end());
if (rev) {
reverse(v.begin(), v.end());
}
deque<int> shit;
int wh = -1;
ll ans = 0;
array<int, 2> last;
for (auto [x, tp]: v) {
last[tp] = x;
if (!shit.empty() and wh != tp) {
ans += abs(x - shit[0]);
shit.pop_front();
} else {
shit.push_back(x);
wh = tp;
}
}
for (int x: shit) ans += abs(x - last[!wh]);
return ans;
}
long long min_total_length(std::vector<int> a, std::vector<int> b) {
int n = a.size(), m = b.size();
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
sort(v.begin(), v.end());
vector<int> fr(v.size(), (int) 1e9);
for (int i = 0; i < v.size(); i++) {
auto [x, tp] = v[i];
if (tp) {
int j = lower_bound(a.begin(), a.end(), x) - a.begin();
if (j < a.size()) fr[i] = min(fr[i], abs(x - a[j]));
j--;
if (j >= 0) fr[i] = min(fr[i], abs(x - a[j]));
} else {
int j = lower_bound(b.begin(), b.end(), x) - b.begin();
if (j < b.size()) fr[i] = min(fr[i], abs(x - b[j]));
j--;
if (j >= 0) fr[i] = min(fr[i], abs(x - b[j]));
}
}
vector<int> pref(v.size());
for (int i = 0; i < v.size(); i++) pref[i] = (i > 0 ? pref[i - 1] : 0) + v[i].second;
vector<ll> pref2(v.size());
for (int i = 0; i < v.size(); i++) pref2[i] = (i > 0 ? pref2[i - 1] : 0) + v[i].first;
vector<ll> dp(v.size(), inf);
array<int, 2> last{-1, -1};
for (int i = 0; i < v.size(); i++) {
dp[i] = (i > 0 ? dp[i - 1] : 0) + fr[i];k
last[v[i].second] = i;
int j = last[!v[i].second];
if (j == -1) continue;
int cnt = i - j;
if (j + 1 < cnt) continue;
int sum = pref[j] - (j - cnt >= 0 ? pref[j - cnt] : 0);
if (v[j].second and sum != cnt) continue;
if (!v[j].second and sum != 0) continue;
// cout << i << ' ' << j << endl;
ll now = (j - cnt >= 0 ? dp[j - cnt] : 0);
now += (pref2[i] - pref2[j]) - (pref2[j] - (j - cnt >= 0 ? pref2[j - cnt] : 0));
dp[i] = min(dp[i], now);
}
return dp.back();
}