//AzaLE (Azamat Alisherov)
#include <bits/stdc++.h>
#include "molecules.h"
#define F first
#define S second
#define size(x) (int)x.size()
using namespace std;
vector <int> find_subset(int l, int r, vector<int> v){
set<pair<int, int>> st;
//using set so no two identical values appear while searching within L and R
//st.F is value;
//st.S is index;
vector <int> inds(size(v));
//using this vector to retrieve answer if it exists-
//-via backtracking indexes
st.insert({0, -1});
for(int i = 0; i < size(v); i++){
int mn = l - v[i];
//searching for appropriate minimum "adder" for L;
auto it = st.lower_bound({mn, 0});
if(it == st.end())it--;
//cout << v[i] << "----> " << mn << " " << (*it).F << " " << (*it).S << endl;
pair<int, int> ins;
ins.F = (*it).F + v[i];
inds[i] = (*it).S;
ins.S = i;
st.insert({v[i], i});
if(ins.F > r)continue;
st.insert(ins);
}
//for(auto [a, b]:st)cout << a << " " << b << endl;
auto it = st.lower_bound({l, -1});
int stind = -1;
//stind (starting index) to backtrack the answer
if((*it).F >= l and (*it).F <= r){
stind = (*it).S;
}
for(int i = 0; i < size(v); i++){
if(v[i] >= l and v[i] <= r){
return {i};
}
}
if(stind == -1){
return {};
}
vector <int> ans;
while(stind >= 0){
ans.push_back(stind);
stind = inds[stind];
}
int res = 0;
for(int i = 0; i < size(ans); i++){
res += v[ans[i]];
}
while(res > r){
res -= v[ans.back()];
ans.pop_back();
}
return ans;
}
/*
*/
Compilation message (stderr)
molecules.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |