Submission #758609

#TimeUsernameProblemLanguageResultExecution timeMemory
758609minhcoolDetecting Molecules (IOI16_molecules)C++17
100 / 100
47 ms10300 KiB
//#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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...