Submission #483870

#	Time	Username	Problem	Language	Result	Execution time	Memory
483870		StrawHatWess	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	292 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
typedef vector<int>vi;

#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//-------------------------------------------------

vi find_subset(int L, int R, vi a) {
    int N=sz(a);
    sort(all(a));
    int l=-1;
    ll cur=0;
    vi pref,suf; 
    while(l+1<N && cur+a[l+1]<=R) l++,cur+=a[l],pref.pb(l);

    if(cur>=L) return pref; 
    ROF(r,l+1,N){
        cur+=a[r]; suf.pb(r); 
        if(sz(pref)){
            cur-=a[pref.back()]; 
            pref.pop_back();
        }
        if(cur>=L && cur<=R){
            vi ans; 
            ans.assign(all(pref));
            for(int x: suf) ans.pb(x);
            return ans; 
        }
    }
    return(vi{});
}

/*
4 15 17
6 8 8 7
*/

/*
4 14 15 
5 5 6 6  
*/

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