| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1060464 |
2024-08-15T15:26:29 Z |
khanhtb |
Sirni (COCI17_sirni) |
C++14 |
|
1122 ms |
747008 KB |
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::pair;
using std::vector;
class DisjointSets {
private:
vector<int> parents;
vector<int> sizes;
public:
DisjointSets(int size) : parents(size), sizes(size, 1) {
for (int i = 0; i < size; i++) { parents[i] = i; }
}
int find(int n) {
return parents[n] == n ? n : (parents[n] = find(parents[n]));
}
bool unite(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) { return false; }
if (sizes[n1] < sizes[n2]) { std::swap(n1, n2); }
sizes[n1] += sizes[n2];
parents[n2] = n1;
return true;
}
};
int main() {
int card_num;
std::cin >> card_num;
vector<int> cards(card_num);
for (int &c : cards) {
std::cin >> c;
assert(c >= 1);
}
std::sort(cards.begin(), cards.end());
// we can erase the dupes bc modding them with the original one = 0
cards.erase(std::unique(cards.begin(), cards.end()), cards.end());
int largest = cards.back(); // since we sorted the cards already
// next_largest[i] contains the index of lowest card value that's >= i
vector<int> next_largest(largest + 1, -1);
for (int i = 0; i < cards.size(); i++) { next_largest[cards[i]] = i; }
for (int c = largest - 1; c >= 0; c--) {
// if this isn't assigned yet, assign it the previous one
if (next_largest[c] == -1) { next_largest[c] = next_largest[c + 1]; }
}
vector<vector<pair<int, int>>> good_links(largest + 1);
for (int i = 0; i < cards.size() - 1; i++) {
// get all relevant cards this card could be connected to
good_links[cards[i + 1] % cards[i]].push_back({i, i + 1});
for (int at = 2 * cards[i]; at <= largest; at += cards[i]) {
int good_mod = next_largest[at];
good_links[cards[good_mod] % cards[i]].push_back({i, good_mod});
}
}
long long total_cost = 0;
DisjointSets linked_cards(cards.size());
for (int c = 0; c <= largest; c++) {
for (const pair<int, int> &link : good_links[c]) {
bool result = linked_cards.unite(link.first, link.second);
total_cost += c * result;
}
}
cout << total_cost << endl;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i < cards.size(); i++) { next_largest[cards[i]] = i; }
| ~~^~~~~~~~~~~~~~
sirni.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < cards.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
274152 KB |
Output is correct |
| 2 |
Correct |
175 ms |
302672 KB |
Output is correct |
| 3 |
Correct |
129 ms |
273492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
753 ms |
668472 KB |
Output is correct |
| 3 |
Correct |
128 ms |
275024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
274536 KB |
Output is correct |
| 2 |
Correct |
118 ms |
273744 KB |
Output is correct |
| 3 |
Correct |
121 ms |
274512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
38280 KB |
Output is correct |
| 2 |
Correct |
100 ms |
66436 KB |
Output is correct |
| 3 |
Correct |
67 ms |
48808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
29784 KB |
Output is correct |
| 2 |
Correct |
64 ms |
51000 KB |
Output is correct |
| 3 |
Correct |
47 ms |
24624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
49688 KB |
Output is correct |
| 2 |
Correct |
119 ms |
83412 KB |
Output is correct |
| 3 |
Correct |
64 ms |
46764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
9660 KB |
Output is correct |
| 2 |
Correct |
128 ms |
84116 KB |
Output is correct |
| 3 |
Correct |
74 ms |
48564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
288336 KB |
Output is correct |
| 2 |
Correct |
809 ms |
633160 KB |
Output is correct |
| 3 |
Correct |
187 ms |
291872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
183 ms |
292384 KB |
Output is correct |
| 2 |
Correct |
1122 ms |
747008 KB |
Output is correct |
| 3 |
Correct |
280 ms |
348532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
276820 KB |
Output is correct |
| 2 |
Correct |
973 ms |
634972 KB |
Output is correct |
| 3 |
Correct |
68 ms |
51132 KB |
Output is correct |
