| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1189243 | Zakir060 | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
// Likely contents of your submission file (e.g., molecules.cpp)
#include <vector>
#include <numeric>
#include <algorithm>
#include <utility> // For std::pair
// Structure to store molecule weight along with its original index
struct Molecule {
long long weight; // Use long long for weight and sums
int index; // Original index (0 to n-1)
};
// Custom comparison function for sorting Molecules in descending order of weight
bool compareMoleculesDesc(const Molecule& a, const Molecule& b) {
if (a.weight != b.weight) {
return a.weight > b.weight;
}
// Consistent tie-breaking (optional but good practice)
return a.index < b.index;
}
/**
* @brief Finds a subset of molecules whose total weight falls within the range [l, u].
*/
std::vector<int> find_subset(int l_int, int u_int, const std::vector<int>& w) {
long long l = l_int;
long long u = u_int;
int n = w.size();
std::vector<Molecule> molecules_to_consider;
molecules_to_consider.reserve(n);
// 1. Filter and Check Single Element Solution
for (int i = 0; i < n; ++i) {
long long current_weight = w[i];
if (current_weight >= l && current_weight <= u) {
return {i};
}
// Only consider molecules with weight <= u for potential combination
if (current_weight <= u) {
molecules_to_consider.push_back({current_weight, i});
}
}
// 2. Sort candidates in descending order by weight
std::sort(molecules_to_consider.begin(), molecules_to_consider.end(), compareMoleculesDesc);
long long current_sum = 0;
std::vector<int> current_subset_indices;
current_subset_indices.reserve(molecules_to_consider.size());
// 3. Greedy Selection (Descending): Add if sum does not exceed u
for (const auto& mol : molecules_to_consider) {
if (current_sum + mol.weight <= u) {
current_sum += mol.weight;
current_subset_indices.push_back(mol.index);
}
}
// 4. Final Check: After considering all candidates, check if the resulting sum is >= l
if (current_sum >= l) {
return current_subset_indices;
} else {
return {}; // Return empty vector
}
}
// --- NO C Interface Wrapper needed if the grader calls the C++ function ---