Submission #138447

#	Time	Username	Problem	Language	Result	Execution time	Memory
138447		Rubanov	Wiring (IOI17_wiring)	C++14	0 / 100	2 ms	504 KiB

wiring

#include <bits/stdc++.h>
#define all(c) c.begin(), c.end()
#define pb push_back
#define ll long long
#define x first
#define y second

using namespace std;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
  int n = r.size();
  int m = b.size();
  bool taken[200005] = {};
  vector<pair<ll,pair<int,int>>> ve;
  for (int i = 0; i < n; i++) {
    int it = lower_bound(all(b),r[i])-b.begin();
    if (it == m) {
      it--;
      ve.pb({r[i]-b[it],{i,it+n}});
    } else {
      int dist = b[it]-r[i];
      int id = it;
      it--;
      if (it >= 0 && r[i]-b[it] < dist) {
        dist = r[i]-b[it];
        id--;
      }
      ve.pb({dist,{i,it+n}});
    }
  }
  for (int i = 0; i < m; i++) {
    int it = lower_bound(all(r),b[i])-r.begin();
    if (it == n) {
      it--;
      ve.pb({b[i]-r[it],{i+n,it}});
    } else {
      int dist = r[it]-b[i];
      int id = it;
      it--;
      if (it >= 0 && b[i]-r[it] < dist) {
        dist = b[i]-r[it];
        id--;
      }
      ve.pb({dist,{i+n,it}});
    }
  }
  sort(all(ve));
  reverse(all(ve));
  ll ans = 0;
  for (auto k : ve) {
    if (taken[k.y.x]) continue;
    taken[k.y.x] = 1;
    taken[k.y.y] = 1;
    ans += k.x;
  }
  return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45