| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1341500 | zowi | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> find_subset(long long l, long long u, std::vector<long long> w) {
ios_base::sync_with_stdio(0);
long long a,b,n,x,m = 1e18,co = -1;
n = w.size();
vector<pair<long long,long long>> tab = {};
for(long long i = 0;i < n;++i)
{
x = w[i];
tab.push_back({x,i});
m = min(m,x);
}
sort(tab.begin(),tab.end());
vector<long long> pre = {0};
for(long long i = 1;i <= n;++i)
{
pre.push_back(pre.back()+tab[i-1].first-m);
}
cin >> l >> u;
for(long long i = 1;i <= n;++i)
{
a = pre[i];
b = pre[n]-pre[n-i];
l -= m;
u -= m;
// cout << l << ' ' << u << ' ' << a << ' ' << b << endl;
if((a <= l && l <= b) || (a <= u && u <= b) || (a <= l && u <= b) || (l <= a && b <= u))
{
co = i;
break;
}
}
l += co*m;
u += co*m;
//cout << l << ' ' << u << endl;
vector<int> wyn1;
if(co == -1)
{
return wyn1;
}
else
{
long long ile = 0;
vector<pair<long long,long long>> wyn;
for(long long i = 1;i <= co;++i)
{
ile += tab[n-i].first;
wyn.push_back(tab[n-i]);
}
long long ind = n-1-co,gdz = 0;
while(ind >= 0 && ile > u)
{
ile -= wyn[gdz].first;
ile += tab[ind].first;
wyn[gdz] = tab[ind];
ind--;
gdz++;
gdz %= co;
}
for(pair<long long,long long> i : wyn)
{
wyn1.push_back(i.second);
}
return wyn1;
}
}