Submission #758607

#TimeUsernameProblemLanguageResultExecution timeMemory
758607minhcoolDetecting Molecules (IOI16_molecules)C++17
9 / 100
1 ms340 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 -= pref[itr];
        sum += pref[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
#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...