Submission #1178818

#TimeUsernameProblemLanguageResultExecution timeMemory
1178818ericl23302Aliens (IOI16_aliens)C++20
4 / 100
5 ms328 KiB
#include "aliens.h" #include <iostream> #include <algorithm> #include <utility> #include <climits> #include <set> using namespace std; long long sq(long long a) { return a * a; } long long sq(int a) { return (long long)(a) * a; } long long getArea(pair<int, int> a) { return sq(a.second - a.first + 1); } long long getArea(int a, int b) { return sq(b - a + 1); } long long intersection(pair<int, int> a, pair<int, int> b) { return sq(max(0, min(a.second, b.second) - max(a.first, b.first) + 1)); } long long unite(pair<int, int> a, pair<int, int> b) { return getArea(min(a.first, b.first), max(a.second, b.second)); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { set<pair<int, int>> curPoints; for (int i = 0; i < n; ++i) curPoints.emplace(min(r[i], c[i]), max(r[i], c[i])); long long leastCost = LLONG_MAX / 2; while (curPoints.size() > k) { leastCost = LLONG_MAX / 2; auto curStart = curPoints.end(), curEnd = curPoints.end(); for (auto i = curPoints.begin(); i != curPoints.end(); ++i) { for (auto j = next(i); j != curPoints.end(); ++j) { auto a = *i, b = *j; long long curCost = unite(a, b) - getArea(a) - getArea(b) + intersection(a, b); if (curCost < leastCost) { leastCost = curCost; curStart = i; curEnd = j; } } } auto a = *curStart, b = *curEnd; pair<int, int> newRange = make_pair(min(a.first, b.first), max(a.second, b.second)); curPoints.erase(curStart); curPoints.erase(curEnd); curPoints.insert(newRange); } vector<pair<int, int>> condensedPoints; int curBegin = -1, curEnd = -1; for (auto i = curPoints.begin(); i != curPoints.end(); ++i) { auto a = *i; if (a.first == curBegin) curEnd = max(curEnd, a.second); else { if (curBegin != -1) condensedPoints.emplace_back(curBegin, curEnd); curBegin = a.first; curEnd = a.second; } } condensedPoints.emplace_back(curBegin, curEnd); auto a = condensedPoints[0]; long long res = getArea(a); for (int i = 1; i < condensedPoints.size(); ++i) { auto b = condensedPoints[i]; if (b.second <= a.second) { continue; } else { res += getArea(b) - intersection(a, b); a = b; } } return res; }

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
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...