Submission #421049

#	Time	Username	Problem	Language	Result	Execution time	Memory
421049		Hegdahl	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	204 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define ar array

using namespace std;
using ll = long long;
using lll = __int128;
using ld = long double;

int n, m, k;
vector<ar<ll, 2>> p;
vector<ll> l, r;
vector<int> s;

const ll INF = 1LL<<60;

ll overlap(ll l0, ll r0, ll l1, ll r1) {
  assert(l0 <= l1);
  assert(l0 <= r0);
  assert(l1 <= r1);

  // completely inside
  if (r1 <= r0) return (r1-l1+1)*(r1-l1+1);

  // completely outside
  if (r0 < l1) return 0;

  return (r0-l1+1)*(r0-l1+1);
}

pair<ll, int> go(ld penalty) {
  ll real_cost = 0;
  int used = 0;
  ll cl = -INF;
  ll cr = -INF;
  
  ld tiebreak = 0;
  ld tiebreak_inc = .5l/n;
  for (int i : s) {
    lll was_w = cr-cl+1;
    lll extend_w = max(cr, r[i]) - min(cl, l[i]) + 1;
    lll extend_cost = extend_w*extend_w - was_w*was_w;

    lll new_w = r[i]-l[i]+1;
    lll new_cost = new_w*new_w - overlap(cl, cr, l[i], r[i]);
    
    if (extend_cost < new_cost + penalty + tiebreak) {
      real_cost += extend_cost;
      cl = min(cl, l[i]);
      cr = max(cr, r[i]);
    } else {
      //if (cl > -INF) cerr << cl << ':' << cr << ' ';

      real_cost += new_cost;
      cl = l[i];
      cr = r[i];
      ++used;
    }

    tiebreak += tiebreak_inc;
  }
  //if (cl > -INF) cerr << cl << ':' << cr << '\n';

  return {real_cost, used};
}

ll take_photos(int n_, int m_, int k_, vector<int> r_, vector<int> c_) {
  n = n_, m = m_, k = k_;
  l.resize(n);
  r.resize(n);
  s.resize(n);
  for (int i = 0; i < n; ++i) {
    l[i] = min(r_[i], c_[i]);
    r[i] = max(r_[i], c_[i]);
  }

  iota(s.begin(), s.end(), 0);
  sort(s.begin(), s.end(), [&](int i, int j) { return l[i] < l[j]; });

  ld lo = 0, hi = 1e18;
  while (hi-lo > 1e-7) {
    ld ce = (hi+lo)/2;
    auto [cost, cnt] = go(ce);
    if (cnt > k) lo = ce;
    else hi = ce;
  }

  auto [ans, cnt] = go(hi);

  lo = hi;
  hi = 1e18;
  while (hi-lo > 1e-7) {
    ld ce1 = lo + (hi-lo)/3;
    ld ce2 = hi - (hi-lo)/3;
    auto [cost1, cnt1] = go(ce1);
    auto [cost2, cnt2] = go(ce2);
    ans = min({ans, cost1, cost2});
    if (cost1 < cost2) lo = ce1;
    else hi = ce2;
  }

  return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40