Submission #172504

#	Time	Username	Problem	Language	Result	Execution time	Memory
172504		golikovnik	Aliens (IOI16_aliens)	C++14	100 / 100	552 ms	18468 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using real_t = long double;

template <typename T>
struct line {
  T k, b;

  [[nodiscard]] T apply(T x) const {
    return k * x + b;
  }
};

template <typename T>
real_t inter(line<T> const& a, line<T> const& b) {
  return static_cast<real_t>(a.b - b.b) / (b.k - a.k);
}

template <typename T>
struct hull {
  struct item {
    line<T> l;
    real_t from;
    real_t to;
    int cnt;

    item(line<T> l_, real_t from_, real_t to_, int cnt_) : l(l_), from(from_)
    , to(to_), cnt(cnt_) {}
  };
  vector<item> lines;
  real_t const inf = 1e20;
  int ptr = 0;

  void add_line(line<T> const& l, int cnt) {
    while ((int) lines.size() >= 2 &&
           inter(l, lines.back().l) <=
           inter(lines.back().l, lines[lines.size() - 2].l)) {
      lines.pop_back();
    }
    if (lines.empty()) {
      lines.emplace_back(l, -inf, inf, cnt);
    } else {
      auto x = inter(l, lines.back().l);
      lines.back().to = x;
      lines.emplace_back(l, x, inf, cnt);
    }
  }

  pair<T, int> get(T x) {
    ptr = min(ptr, (int) lines.size() - 1);
    while (x > lines[ptr].to) {
      ++ptr;
    }
    return {lines[ptr].l.apply(x), lines[ptr].cnt};
  }
};

i64 take_photos(int n, int, int mx, vector<int> r, vector<int> c) {
  struct cell {
    int r, c;

    cell(int r_, int c_) : r(r_), c(c_) {}
  };
  vector<cell> a;
  {
    for (int i = 0; i < n; ++i) {
      if (r[i] < c[i]) {
        swap(r[i], c[i]);
      }
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
      if (r[i] != r[j]) {
        return r[i] < r[j];
      }
      return c[i] > c[j];
    });
    for (int i = 0; i < n; ++i) {
      while (!a.empty() && a.back().c >= c[p[i]]) {
        a.pop_back();
      }
      a.emplace_back(r[p[i]], c[p[i]]);
    }
  }
  n = (int) a.size();
  mx = min(mx, n);
  auto calc = [&](i64 lam) -> pair<i64, int> {
    auto sqr = [](i64 x) {
      return x * x;
    };
    hull<i64> cht;
    i64 cur = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      auto ci = !i ? 0 : sqr(
              max<i64>(0, a[i - 1].r - a[i].c + 1));
      cht.add_line({-2 * a[i].c, sqr(a[i].c) + cur - ci},
                   cnt);
      auto res = cht.get(a[i].r + 1);
      cnt = res.second + 1;
      cur = sqr(a[i].r + 1) + res.first + lam;
    }
    return {cur, cnt};
  };
  i64 left = 0;
  i64 right = (i64) 1e13;
  while (left + 1 != right) {
    auto middle = (left + right) / 2;
    auto[score, nsqs] = calc(middle);
    if (nsqs > mx) {
      left = middle;
    } else {
      right = middle;
    }
  }
  auto get_cost = [](auto p, auto lam) {
    return p.first - p.second * lam;
  };
  auto f_right = calc(right);
  if (f_right.second == mx) {
    return get_cost(f_right, right);
  }
  auto f_left = calc(left);
  if (f_left.second == mx) {
    return get_cost(f_left, left);
  }

  auto k = static_cast<long double>(get_cost(f_left, left) - get_cost(f_right,
          right)) /
          (f_left.second - f_right.second);
  auto b = get_cost(f_left, left) - k * f_left.second;
  return (i64) roundl(k * mx + b);
}

//i64 take_photos_ac(int n, int, int mx, vector<int> r, vector<int> c) {
//  struct cell {
//    int r, c;
//
//    cell(int r_, int c_) : r(r_), c(c_) {}
//  };
//  vector<cell> a;
//  {
//    for (int i = 0; i < n; ++i) {
//      if (r[i] < c[i]) {
//        swap(r[i], c[i]);
//      }
//    }
//    vector<int> p(n);
//    iota(p.begin(), p.end(), 0);
//    sort(p.begin(), p.end(), [&](int i, int j) {
//      if (r[i] != r[j]) {
//        return r[i] < r[j];
//      }
//      return c[i] > c[j];
//    });
//    for (int i = 0; i < n; ++i) {
//      while (!a.empty() && a.back().c >= c[p[i]]) {
//        a.pop_back();
//      }
//      a.emplace_back(r[p[i]], c[p[i]]);
//    }
//  }
//  n = (int) a.size();
//  mx = min(mx, n);
//  i64 const INF = (i64) 1e18;
//  vector<vector<i64>> dp(n + 1, vector<i64>(mx + 1, INF));
//  fill(dp[0].begin(), dp[0].end(), 0);
//  auto relax = [&](i64& x, i64 y) {
//    if (y < x) {
//      x = y;
//    }
//  };
//  auto sqr = [](i64 x) {
//    return x * x;
//  };
//  for (int k = 1; k <= mx; ++k) {
//    hull<i64> cht;
//    for (int i = 0; i < n; ++i) {
//      //  dp[i + 1][k]
//      auto ci = !i ? 0 : sqr(
//              max<i64>(0, a[i - 1].r - a[i].c + 1));
//      cht.add_line({-2 * a[i].c, sqr(a[i].c) + dp[i][k - 1] - ci}, 0);
//      dp[i + 1][k] = sqr(a[i].r + 1) + cht.get(a[i].r + 1).first;
//    }
//  }
//  return dp.back().back();
//}

//#define STRESS
//
//int main() {
//#ifdef STRESS
//  mt19937 rng(566);
//  auto rnd = [&](auto from, auto to) {
//    return uniform_int_distribution<decltype(from)>(from, to)(rng);
//  };
//  int const N = 30;
//  int const M = 30;
//  for (int it = 0; ; ++it) {
//    cerr << it << '\n';
//    if (it == 4) {
//      cerr << "elegiggle\n";
//    }
//    int n = rnd(1, N);
//    int m = rnd(1, M);
//    vector<int> r(n);
//    vector<int> c(n);
//    for (int i = 0; i < n; ++i) {
//      r[i] = rnd(0, m - 1);
//      c[i] = r[i];
//    }
//    int k = rnd(1, n);
//    auto ac = take_photos_ac(n, m, k, r, c);
//    auto wa = take_photos(n, m, k, r, c);
//    if (ac != wa) {
//      cout << ac << ' ' << wa << endl;
//      cout << n << ' ' << m << ' ' << k << endl;
//      for (int i = 0; i < n; ++i) {
//        cout << r[i] << ' ' << c[i] << endl;
//      }
//      return 0;
//    }
//    cout << "passed " << ac << endl;
//  }
//#else
//  vector<int> r{2, 3, 4, 5};
////  vector<int> r{1, 2, 3, 4};
//  auto c = r;
//  int m = 6;
//  int k = 3;
//  cout << take_photos((int) r.size(), m, k, r, c) << '\n';
//#endif
//}
//
///*
// 6 8
//  4 6 3
//  2 2
//  4 4
//  3 3
//  5 5
// */

Compilation message (stderr)

aliens.cpp: In function 'i64 take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:113:9: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto[score, nsqs] = calc(middle);
         ^
aliens.cpp:113:21: warning: unused variable 'score' [-Wunused-variable]
     auto[score, nsqs] = calc(middle);
                     ^

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