Submission #758609

#	Time	Username	Problem	Language	Result	Execution time	Memory
758609		minhcool	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	47 ms	10300 KiB

molecules

//#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].fi;
        sum += w[n - itr - 1].fi;
    }
    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

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31