Submission #982203

#	Time	Username	Problem	Language	Result	Execution time	Memory
982203		totoro	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	600 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 <climits>
#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;
    long long next;
    Range(long long start, long long end) : start(start), end(end), next(-1){};
    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);
    }
};

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) {
            if (!ranges.empty()) {
                ranges.back().next = ranges.size();
            }
            ranges.emplace_back(point.row, point.col);
            area += (point.col - point.row + 1) * (point.col - point.row + 1);
            if (point.row <= furthestEnd) {
                area -= (furthestEnd - point.row + 1) * (furthestEnd - point.row + 1);
            }
            furthestStart = point.row;
            furthestEnd = point.col;
        }
    }

    size_t excludedCount = 0;
    while (ranges.size() - excludedCount > k) {
        long long bestAmount = LLONG_MAX;
        size_t bestIndex = 0;
        for (long long i = 0; ranges[i].next != -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:39:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     for (size_t i = 0; i < n; ++i) {
      |                        ~~^~~
aliens.cpp:65:42: warning: comparison of integer expressions of different signedness: 'std::vector<Range>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |     while (ranges.size() - excludedCount > k) {
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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