# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1015002 | ziyad_alharbi | 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 <bits/stdc++.h>
using namespace std;
int n;
int L, R;
pair<long long, long long>wh[200005];
bool b;
set<int>st;
void f(int x,long long s)
{
//cout << x << ' ';
if (s >= L&&!b)
{
b = 1;
return;
}
if (x == n || b || wh[x].first + s > R)return;
//cout << x << ' ' << s << '\n';
g.insert({ x,s });
f(x + 1, s + wh[x].first);
if (b)return;
st.erase(wh[x].second);
f(x + 1, s);
}
vector<int> find_subset(int l, int u, vector<int> w)
{
n = w.size();
long long s = 0;
for (int x = 0; x < n; x++)
{
wh[x].first = w[x];
wh[x].second = x;
s += w[x];
}
sort(wh, wh + n);
L = l;
R = u;
if (s >= L && s <= R)
{
vector<int>a;
for (int x = 0; x < n; x++)
{
a.push_back(x);
}
return a;
}
else if (s < L)
{
return vector<int>(0);
}
f(0, 0);
if (st.size())
{
vector<int>a;
for (auto i : st)
{
a.push_back(i);
}
return a;
}
else
{
return vector<int>(0);
}
}
/*signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin>>t;
while (t--)
{
int N, L, R;
cin >> N >> L >> R;
vector<int> w(N);
for (int x = 0; x < N; x++)
{
cin >> w[x];
}
vector<int>a = find_subset(L, R, w);
int nh = a.size();
for (int x = 0; x < nh; x++)cout << a[x] << ' ';
}
return 0;
}*/