# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
982168 |
2024-05-14T01:54:08 Z |
totoro |
Aliens (IOI16_aliens) |
C++17 |
|
0 ms |
584 KB |
// 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;
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) {
ranges.emplace_back(point.row, point.col, i + 1);
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 (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
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:62:42: warning: comparison of integer expressions of different signedness: 'std::vector<Range>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
62 | while (ranges.size() - excludedCount > k) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
584 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
428 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
5 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 91, expected = 41 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
584 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
428 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 91, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
584 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
428 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 91, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
584 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
428 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 91, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
584 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
428 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 91, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |