This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
#define fi first
#define sc second
vector<int> getans(set<pii> s){
vector<int> t;
for(auto c : s){
t.push_back(c.second);
}
sort(t.begin(), t.end());
return t;
}
vector<int> find_subset(int l, int u, vector<int> w){
int n = w.size();
ll ans = 0;
for(int i : w) ans += i;
if(l <= ans && ans <= u){
vector<int> ans(n);
iota(ans.begin(), ans.end(), 0);
return ans;
};
vector<pii> p;
for(int i = 0; i < n; ++i){
p.push_back({w[i], i});
}
sort(p.begin(), p.end());
if(ans < l) return {};
set<pii> s; ans = 0;
for(int i = 0; i < n; ++i){
ans += p[i].first;
s.insert(p[i]);
if(ans < l) continue;
if(l <= ans && ans <= u){
return getans(s);
}
if(ans > u){
auto itr = s.lower_bound(make_pair(ans - u, INT_MIN));
if(itr == s.end()) itr--;
ans -= itr->first; s.erase(itr);
if(l <= ans && ans <= u) return getans(s);
}
}
return {};
}
// int main(){
// int n, l, u; cin >> n >> l >> u;
// vector<int> a(n);
// for(int &x : a) cin >> x;
// vector<int> ans = find_subset(l, u, a);
// for(int i : ans) cout << i << ' ';
// return 0;
// }
# | 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... |