# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
758608 | minhcool | 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.
//#define local
#ifndef local
#include "molecules.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;
const ll N = 3e5 + 5;
const ll oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
ll rnd(ll l, ll r){
ll temp = rng() % (r - l + 1);
return abs(temp) + l;
}
ll pref[N], suff[N];
ii w[N];
vector<int> find_subset(int l, int u, vector<int> W) {
//return vector<ll>(0);
ll n = W.size();
for(ll i = 0; i < n; i++) w[i] = {W[i], i};
sort(w, w + n);
for(ll i = 0; i < n; i++) pref[i] = suff[i] = w[i].fi;
for(ll i = 1; i < n; i++) pref[i] += pref[i - 1];
for(ll i = n - 2; i >= 0; i--) suff[i] += suff[i + 1];
ll ind = -1;
vector<int> ans;
for(ll num = 1; num <= n; num++){
if(pref[num - 1] > u) return ans;
if(suff[n - num] >= l){
ind = num;
break;
}
}
if(ind < 0) return ans;
ll sum = pref[ind - 1], itr = -1;
while(sum < l){
itr++;
sum -= w[itr];
sum += w[n - itr - 1];
}
assert(itr < ind);
vector<int> v;
for(ll i = itr + 1; i < ind; i++) v.pb(w[i].se);
for(ll i = n - 1; i >= (n - 1 - itr); i--) v.pb(w[i].se);
sort(v.begin(), v.end());
return v;
}
//#define local
#ifdef local
void process(){
ll n, l, u;
cin >> n >> l >> u;
vector<int> v;
for(ll i = 0; i < n; i++){
ll x;
cin >> x;
v.pb(x);
}
vector<int> v2 = find_subset(l, u, v);
for(auto it : v2) cout << it << " ";
cout << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
#endif