Submission #484445

#	Time	Username	Problem	Language	Result	Execution time	Memory
484445		StrawHatWess	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	42 ms	6708 KiB

molecules

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

typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pi;
typedef vector<pi>vpi;
#define fi first
#define se second

#define pb push_back
#define eb emplace_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);

    vpi a; 
    FOR(i,0,N) a.eb(A[i],i);
    sort(all(a));

    int l=-1;
    ll cur=0;
    vi pref,suf; 
    while(l+1<N && cur+a[l+1].fi<=R){
        l++; 
        cur+=a[l].fi;
        pref.pb(a[l].se);
    }

    if(cur>=L) return pref; 
    ROF(r,0,N){
        cur+=a[r].fi; suf.pb(a[r].se); 
        if(sz(pref)){
            cur-=A[pref.back()]; 
            pref.pop_back();
        }
        else break;
        if(cur>=L){
            vi ans; 
            for(int x: pref) ans.pb(x);
            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: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31