# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1000365 | Gray | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 0 KiB |
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 <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <stack>
#include <vector>
#define ll long long
#define ld double
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll MOD = (ll)1e9+7;
const ll INF = 2e18;
vector<int> find_subset(int d, int u, vector<int> &w){
ll n = w.size();
vector<pair<ll, ll>> iw(n);
for (ll i=0; i<n; i++) iw[i] = {w[i], i};
sort(iw.begin(), iw.end());
ll l=0, r=0;
ll sum=iw[0].ff;
while (r<n){
if (sum<=u){
if (sum>=d){
vector<int> ans;
ll rsum=0;
for (ll i=l; i<=r; i++){
rsum+=iw[i].ff;
ans.push_back(iw[i].ss);
}
assert(rsum<=u and rsum>=d);
return ans;
}else{
r++;
sum+=iw[r].ff;
}
}else{
sum-=iw[l].ff;
l++;
}
}
return {};
}