Submission #982158

#	Time	Username	Problem	Language	Result	Execution time	Memory
982158		totoro	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

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

#include "aliens.h"

#include <algorithm>
#include <unordered_set>
#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;
    size_t next;
    Range(long long start, long long end, size_t next) : start(start), end(end), next(next){};
    long long merge(const Range& other) const {
        return 2 * (other.start - start) * (other.end - end) - (other.start <= end ? (end - other.start - 1) * (end - other.start - 1) : 0);
    }
};

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());

    long long area = 0;
    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) {
            furthestStart = point.row;
            furthestEnd = point.col;
            ranges.emplace_back(point.row, point.col, i + 1);
            area += (point.col - point.row + 1) * (point.col - point.row + 1);
        }
    }

    size_t excludedCount = 0;
    while (ranges.size() - excludedCount > k) {
        long long bestAmount = LLONG_MAX;
        size_t bestIndex = 0;
        for (size_t i = 0; i < ranges.size() - 1; i = ranges[i].next) {
            long long score = ranges[i].merge(ranges[ranges[i].next]);
            if (score < bestAmount) {
                bestAmount = score;
                bestIndex = i;
            }
        }
        ranges[bestIndex].end = ranges[ranges[bestIndex].next].end;
        area += bestAmount;
        ranges[bestIndex].next = ranges[ranges[bestIndex].next].next;
        ++excludedCount;
    }

    return area;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:38:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     for (size_t i = 0; i < n; ++i) {
      |                        ~~^~~
aliens.cpp:58:42: warning: comparison of integer expressions of different signedness: 'std::vector<Range>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     while (ranges.size() - excludedCount > k) {
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
aliens.cpp:59:32: error: 'LLONG_MAX' was not declared in this scope
   59 |         long long bestAmount = LLONG_MAX;
      |                                ^~~~~~~~~
aliens.cpp:14:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
   13 | #include <unordered_set>
  +++ |+#include <climits>
   14 | #include <vector>