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 "molecules.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define int ll
#define sz(x) (int)(x).size()
using pii = pair<int,int>;
#undef int
std::vector<int> find_subset(int l, int u, std::vector<int> Wprim) {
#define int ll
vector<ll> W;
W.reserve(sz(Wprim));
for(auto x : Wprim)
W.emplace_back(x);
ll summine = 0;
for(auto x : W) summine += x;
if(summine < l) return vector<signed>(0);
vector<pii> w;
for(auto x : W)
w.emplace_back(x, sz(w));
sort(all(w));
if(l <= w.back().first && w.back().first <= u) return vector<signed>(1, w.back().second);
if(w[0].first > u) return vector<signed>(1, 2);
vector<signed> rez;
int sum = 0;
for(int i = 0; i < sz(w); i++) {
sum += w[i].first;
if(sum > u) { sum -= w[i].first; break; }
rez.emplace_back(w[i].second);
}
if(l <= sum && sum <= u) return rez;
//cerr << sum << ' ';
//for(auto x : rez) cerr << x << ' ';
//cerr << '\n';
vector<signed> replace;
cerr << sz(rez) << '\n';
for(int i = sz(w) - 1; sz(rez) && i >= 0; i--) {
if(l <= sum && sum <= u) break;
auto cv = W[rez.back()];
sum += w[i].first - cv;
rez.pop_back();
replace.emplace_back(w[i].second);
cerr << sum << ' ';
}
if(sum < l) return vector<signed>(1, 2);
copy(all(replace), back_inserter(rez));
return rez;
}
#undef int
# | 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... |