Submission #788302

#	Time	Username	Problem	Language	Result	Execution time	Memory
788302		NeroZein	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	340 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std; 

long long min_total_length(std::vector<int> r, std::vector<int> b) {
  if (r.size() > b.size()) {
    swap(r, b); 
  }
  int n = (int) r.size();
  int m = (int) b.size(); 
  auto dis = [&](int i, int j) {
    return abs(i - j); 
  };
  sort(r.begin(), r.end());
  sort(b.begin(), b.end()); 
  int p = 0;
  vector<int> a(m);  
  long long ans = 0; 
  for (int i = 0; i < n; ++i) {
    while (p + 1 < m && dis(r[i], b[p]) > dis(r[i], b[p + 1])) {
      p++; 
    }
    ans += dis(r[i], b[p]); 
    a[p]++;
  }
  int give = 0;
  stack<int> take;
  for (int i = m - 1; i >= 0; --i) {
    while (take.size() && a[i] > 1) {
      ans -= a[i];
      a[take.top()] = 1;
      take.pop(); 
    }
    while (a[i] > 1) {
      ans += a[i];
      give++;
      a[i]--;
    }
    if (a[i] == 0) {
      if (give) {
        ans -= a[i];
        give--;
      } else {
        take.push(i); 
        ans += a[i]; 
      }
    }
  }
  assert(give == 0); 
  assert((int) take.size() == m - n); 
  p = 0; 
  for (int i = 0; i < m; ++i) {
    while (p + 1 < n && dis(r[p], b[i]) > dis(r[p + 1], b[i])) {
      p++; 
    }
    if (a[i] == 0) {
      ans += dis(r[p], b[i]);       
    }
  }
  return ans; 
}

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