Submission #1176087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176087		totoro	Aliens (IOI16_aliens)	C++17	41 / 100	2095 ms	8884 KiB

aliens

// SOLVED SUBTASK 1   (04 pts)
// SOLVED SUBTASK 2   (12 pts)
// SOLVED SUBTASK 3   (09 pts)
// SOLVED SUBTASK 4   (16 pts)
// SOLVED SUBTASK 5   (19 pts)
// UNSOLVED SUBTASK 6 (40 pts)
// [+-+]----------------------
// TOTAL     60/100 pts

#include "aliens.h"

#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <vector>

struct Coordinate {
    long long row, col;
    Coordinate(long long row, long long col) : row(std::min(row, col)), col(std::max(row, col)) {}
    bool operator<(const Coordinate& other) const {
        if (row == other.row) {
            return col > other.col;
        }
        return row < other.row;
    }
};

struct Range {
    long long start, end;
    Range(long long start, long long end) : start(start), end(end) {};
    long long merge(const Range& other) const {
        return 2 * (other.start - start) * (other.end - end) - (other.start > end ? (other.start - end - 1) * (other.start - end - 1) : 0);
    }
};

struct Parabola {
    __float128 h, v;

    __float128 evaluate(__float128 x) {
        return (x - h) * (x - h) + v;
    }
};

__float128 intersect(Parabola a, Parabola b) {
    return (b.h * b.h + b.v - a.h * a.h - a.v) / (2.0 * (b.h - a.h));
}

struct ConvexHull {
    std::vector<Parabola> parabolas;
    std::vector<__float128> left;
    std::vector<int> indexes;
    std::vector<int> cnts;
    std::map<__float128, int> mp;
    int counter = 0;

    void insert(Parabola p, int cnt) {
        while (!parabolas.empty() && intersect(p, parabolas.back()) < left.back()) {
            parabolas.pop_back();
            mp.erase(left.back());
            left.pop_back();
            indexes.pop_back();
            cnts.pop_back();
        }
        if (parabolas.empty()) {
            parabolas.push_back(p);
            left.push_back(-1e18);  // neg infty
            indexes.push_back(counter);
        } else {
            __float128 x = intersect(p, parabolas.back());
            parabolas.push_back(p);
            left.push_back(x);
            if (mp.count(x)) {
                if (cnt > cnts[mp[x]]) {
                    mp[x] = parabolas.size() - 1;
                }
            } else {
                if (cnts.back() > cnt) {
                    mp[x] = parabolas.size() - 2;
                } else {
                    mp[x] = parabolas.size() - 1;
                }
            }
            indexes.push_back(counter);
        }
        cnts.push_back(cnt);
        ++counter;
        // std::cout << "inserted (x-" << p.h << ")^2 + " << p.v << '\n';
    }

    std::pair<int, __float128> min(__float128 x) {
        int index = std::upper_bound(left.begin(), left.end(), x) - left.begin() - 1;
        if (mp.count(x)) {
            int index = mp[x];
        }
        return {indexes[index], parabolas[index].evaluate(x)};
    }
};

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    std::vector<Coordinate> points;
    for (size_t i = 0; i < n; ++i) {
        points.push_back(Coordinate(r[i], c[i]));
    }
    std::sort(points.begin(), points.end());

    std::vector<Range> ranges;
    long long furthestStart = -1;
    long long furthestEnd = -1;
    for (size_t i = 0; i < points.size(); ++i) {
        Coordinate point = points[i];
        if (point.row > furthestStart && point.col > furthestEnd) {
            ranges.emplace_back(point.row, point.col);
            furthestStart = point.row;
            furthestEnd = point.col;
        }
    }
    ranges.push_back({(long long)1e15, (long long)1e15});

    __float128 lo = 0, hi = 5e13;
    while (lo < hi - 0.00005) {
        __float128 penalty = lo + (hi - lo) / 2.0;
        ConvexHull hull;
        std::vector<long long> cnt;
        hull.insert(Parabola{(__float128)ranges[0].start, 0.0}, 0);
        cnt.push_back(0);
        for (size_t range = 0; range < ranges.size() - 1; ++range) {
            auto [from, best] = hull.min(ranges[range].end + 1);
            hull.insert(Parabola{(__float128)ranges[range + 1].start, (__float128)best - std::pow(std::max(0ll, ranges[range].end - ranges[range + 1].start + 1), 2) + penalty}, cnt[from] + 1);
            cnt.push_back(cnt[from] + 1);
        }
        if (cnt.back() >= k) {
            // std::cout << "if we penalise by " << penalty << ", we want to take " << cnt.back() << '\n';
            lo = penalty;
            // std::cout << "update lo\n";
        } else {
            hi = penalty;
            // std::cout << "update hi\n";
        }
    }
    __float128 penalty = hi;
    __float128 ans = 0;
    {
        ConvexHull hull;
        std::vector<long long> cnt;
        hull.insert(Parabola{(__float128)ranges[0].start, 0.0}, 0);
        cnt.push_back(0);
        for (size_t range = 0; range < ranges.size() - 1; ++range) {
            auto [from, best] = hull.min(ranges[range].end + 1);
            hull.insert(Parabola{(__float128)ranges[range + 1].start, (__float128)best - std::pow(std::max(0ll, ranges[range].end - ranges[range + 1].start + 1), 2) + penalty}, cnt[from] + 1);
            cnt.push_back(cnt[from] + 1);
            ans = best + penalty;
        }
    }
    // std::cout << penalty << '\n';
    return ans - std::min(k, (int)ranges.size() - 1) * lo;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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