| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1189242 | Zakir060 | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
#include <vector> // For std::vector
#include <numeric> // Potentially useful, but not strictly needed here
#include <algorithm> // For std::sort
#include <utility> // For std::pair
/*
* This implementation is for the C++ interface where the function
* directly returns a std::vector<int>.
* A C interface adapter is provided further down.
*/
// Structure to store molecule weight along with its original index
struct Molecule {
long long weight; // Use long long for weight to handle potential large values and sums
int index; // Original index (0 to n-1)
};
// Custom comparison function for sorting Molecules in descending order of weight.
// If weights are equal, sorting by index makes the result deterministic (though not required).
bool compareMoleculesDesc(const Molecule& a, const Molecule& b) {
if (a.weight != b.weight) {
return a.weight > b.weight; // Primary sort: higher weight first
}
return a.index < b.index; // Secondary sort: lower index first (arbitrary but consistent)
}
/**
* @brief Finds a subset of molecules whose total weight falls within the range [l, u].
*
* @param l_int The lower bound of the detection range (inclusive).
* @param u_int The upper bound of the detection range (inclusive).
* @param w A constant reference to a vector containing the weights of the molecules.
* @return A vector containing the original indices (0-based) of the molecules
* in a valid subset. Returns an empty vector if no such subset exists.
*
* @details
* The algorithm leverages the problem's constraint that u - l >= w_max - w_min.
* It employs a greedy strategy:
* 1. Filter out molecules heavier than the upper bound 'u'.
* 2. Immediately return if any single molecule's weight falls within [l, u].
* 3. Sort the remaining potential candidate molecules (those with weight <= u)
* in descending order of weight.
* 4. Greedily add molecules from the sorted list (heaviest first) to a running sum,
* as long as the sum does not exceed 'u'.
* 5. After trying all candidates, check if the final sum is greater than or equal to 'l'.
* If it is, the indices of the molecules added form a valid subset.
* Otherwise (if the final sum is less than 'l'), no subset satisfying the
* conditions exists according to this greedy strategy, and due to the problem's
* constraint, this implies no solution exists at all.
*/
std::vector<int> find_subset(int l_int, int u_int, const std::vector<int>& w) {
// Use long long for bounds and sums to prevent potential overflow,
// as n * max(w) can exceed 32-bit limits.
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); // Reserve space for efficiency
// 1. Filter molecules and Check for Single-Molecule Solutions
for (int i = 0; i < n; ++i) {
long long current_weight = w[i]; // Use long long consistently
// Check if this single molecule is already a valid subset
if (current_weight >= l && current_weight <= u) {
return {i}; // Found a solution with just one molecule
}
// Only consider molecules with weight <= u for potential combination.
// Molecules with weight > u cannot be part of any valid sum <= u.
// We also implicitly ignore molecules with weight >= l here because
// they were handled by the single-molecule check above.
if (current_weight < l) { // Only molecules lighter than l need combining
molecules_to_consider.push_back({current_weight, i});
}
// If current_weight > u, it's simply not added.
}
// 2. Sort the candidates (those with weight < l) in descending order
std::sort(molecules_to_consider.begin(), molecules_to_consider.end(), compareMoleculesDesc);
long long current_sum = 0;
std::vector<int> current_subset_indices;
// Optimization: Reserve capacity close to the number of candidates
current_subset_indices.reserve(molecules_to_consider.size());
// 3. Greedy Selection (Descending Order)
// Iterate through the sorted candidate molecules (heaviest first)
for (const auto& mol : molecules_to_consider) {
// Add the molecule to the subset if doing so does NOT exceed the upper bound 'u'.
if (current_sum + mol.weight <= u) {
current_sum += mol.weight;
current_subset_indices.push_back(mol.index);
// OPTIONAL check: If the sum reaches the target range [l, u]
// we could potentially return immediately. However, the standard
// greedy approach here finishes building the sum first. Let's stick
// to the logic of building the largest possible sum <= u first.
// if (current_sum >= l) {
// return current_subset_indices; // Early exit if sum enters range
// }
}
}
// 4. Final Check
// After iterating through all potential candidates, check if the accumulated sum
// meets the lower bound 'l'. We already know current_sum <= u from the loop condition.
if (current_sum >= l) {
// The greedy approach successfully found a subset sum within [l, u]
return current_subset_indices;
} else {
// The largest sum constructible greedily (descending) without exceeding 'u'
// is still less than 'l'. The problem's constraint implies no other subset
// will work either.
return {}; // Return an empty vector indicating no solution found
}
}
// --- C Interface Adapter ---
// This part provides the wrapper function required for the C language interface.
// It assumes the C++ function `find_subset` defined above is available.
#ifdef __cplusplus
extern "C" {
#endif
// We need C++ standard library headers if this were compiled separately.
// Assuming they are available from the C++ code above.
/**
* @brief C interface function to find a subset sum in range [l, u].
*
* @param l_int The lower bound of the detection range.
* @param u_int The upper bound of the detection range.
* @param w_arr Array of molecule weights.
* @param n The number of molecules.
* @param result Output array (pre-allocated, assumed size n) to store indices
* of the found subset.
* @return The number of elements in the found subset (size of the subset),
* or 0 if no such subset exists.
*/
int find_subset_c_interface(int l_int, int u_int, int* w_arr, int n, int* result) {
// Create a C++ std::vector from the input C array for convenience
std::vector<int> w_vec(w_arr, w_arr + n);
// Call the core C++ function implementation
std::vector<int> subset_indices = find_subset(l_int, u_int, w_vec);
// Process the result for the C interface
if (!subset_indices.empty()) {
int count = 0;
// Copy the indices from the result vector to the C array 'result'
for (int index : subset_indices) {
// It's assumed 'result' is large enough to hold 'n' elements.
result[count++] = index;
}
return count; // Return the number of indices found
} else {
// No subset was found
return 0;
}
}
#ifdef __cplusplus
} // extern "C"
#endif