Submission #556169

#	Time	Username	Problem	Language	Result	Execution time	Memory
556169		Sweezy	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2077 ms	6052 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
 
const int inf = 1e18;
 
void solve() {
  int k, n;
  cin >> k >> n;
  int add = 0;
  vector<int> coords;
  vector<pair<int, int>> needs;
  for (int i = 0; i < n; i++) {
    char t1, t2;
    int x1, x2;
    cin >> t1 >> x1 >> t2 >> x2;
    if (t1 == t2) {
      add += abs(x1 - x2);
    } else {
      add++;
      if (t1 == 'B') {
        swap(x1, x2);
      }
      coords.push_back(x1);
      coords.push_back(x2);
      needs.emplace_back(x1, x2);
    }
  }
 
  int cs = coords.size();
  if (cs == 0) {
    cout << add;
    return;
  }
  sort(coords.begin(), coords.end());
 
  if (k == 1) {
    int x = coords[cs / 2];
    int res = 0;
    for (int i = 0; i < cs; i++) {
      res += abs(coords[i] - x);
    }
    cout << res + add;
  } else {
 
    auto f = [&] (int l, int r) {
      l = coords[l];
      r = coords[r];
      int res = 0;
      for (int i = 0; i < cs / 2; i++) {
        res += min(abs(l - needs[i].first) + abs(l - needs[i].second), abs(r - needs[i].first) + abs(r - needs[i].second));
      }
      return res;
    };
 
    int best = inf;
    for (int i = 0; i < cs; i++) {
      int l = 0, r = i;
      while (r - l > 3) {
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        if (f(m1, i) > f(m2, i)) {
          l = m1;
        } else {
          r = m2;
        }
      }
      for (int j = l; j <= r; j++) {
        best = min(best, f(j, i));
      }
    }
 
    cout << best + add;
  }
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37