| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 73265 | nvmdava | Wiring (IOI17_wiring) | C++17 | 0 ms | 0 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 "wiring.h"
#define INF 2000000005
#include <bits/stdc++.h>
using namespace std;
struct Path{
int r, b, len;
Path(int _r, int _b, int _len){
r = _r;
b = _b;
len = _len;
}
bool operator<(const Path& rhs) const{
return len < rhs.len;
}
};
vector<Path> v;
int rr[100007], bb[100007];
int conr[100007], conb[100007];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
r.push_back(INF);
b.push_back(INF);
bb[0] = 0;
rr[0] = 0;
long long ans = 0;
for(int i = 1; i < b.size(); i++){
bb[i] = upper_bound(r.begin() + bb[i - 1], r.end(), (b[i] + b[i - 1]) / 2) - r.begin();
}
for(int i = 1; i < r.size(); i++){
rr[i] = upper_bound(b.begin() + rr[i - 1], b.end(), (r[i] + r[i - 1]) / 2) - b.begin();
}
for(int i = 0; i < b.size(); i++){
for(int j = bb[i]; j < bb[i + 1]; j++){
v.push_back(Path(j, i, abs(r[j] - b[i])));
}
}
for(int i = 0; i < r.size(); i++){
for(int j = rr[i]; j < rr[i + 1]; j++){
v.push_back(Path(i, j, abs(r[i] - b[j])));
}
}
sort(v.begin(), v.end());
for(auto x : v){
if(conr[x.r] == 0 || conb[x.b] == 0){
conr[x.r]++;
conb[x.b]++;
ans += x.len;
}
}
for(auto x : boost::adaptors::reverse(v)){
if(conr[x.r] > 1 && conb[x.b] > 1){
conr[x.r]--;
conb[x.b]--;
ans -= x.len;
}
}
return ans;
}
int main() {
int n, m;
assert(2 == scanf("%d %d", &n, &m));
vector<int> r(n), b(m);
for(int i = 0; i < n; i++)
assert(1 == scanf("%d", &r[i]));
for(int i = 0; i < m; i++)
assert(1 == scanf("%d", &b[i]));
long long res = min_total_length(r, b);
printf("%lld\n", res);
return 0;
}