# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1243069 | Circling | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <iomanip>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstdint>
#include "molecules.h"
using namespace std;
vector<int> find_subset(int64_t l, int64_t u, vector<int64_t> w){
vector<pair<int64_t, int>> arr;
for (int i = 0; i < w.size(); i++) arr.push_back({w[i], i + 1});
sort(arr.begin(), arr.end());
int64_t prefsum = 0, sufsum = 0, len = 0, currsum;
while (len < w.size() && sufsum < l){
prefsum += arr[len].first;
sufsum += arr[w.size() - 1 - len].first;
len++;
}
if (len > w.size() || prefsum > u) return {};
vector<int> indices, ans;
for (int i = 0; i < len; i++) indices.push_back(i);
currsum = prefsum;
for (int i = 0; currsum < l; i++){
currsum -= arr[indices[i]].first;
indices[i] += len;
currsum += arr[indices[i]].first;
}
for (int i = 0; i < len; i++) ans.push_back(arr[indices[i]].second);
return ans;
}