Submission #940807

#	Time	Username	Problem	Language	Result	Execution time	Memory
940807		Lalic	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	43 ms	11076 KiB

molecules

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

#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

vector<int> find_subset(int l, int u, vector<int> w) {
    int n=(int)w.size();
    
    vector<pll> tr;
    for(int i=0;i<n;i++) tr.pb({w[i], i});
    sort(all(tr));
    
    vector<ll> pref(n+1); pref[0]=0;
    for(int i=1;i<=n;i++) pref[i]=pref[i-1]+tr[i-1].fi;
    
    vector<ll> suff(n+1); suff[0]=0;
    for(int i=1;i<=n;i++) suff[i]=suff[i-1]+tr[n-i].fi;
    
    vector<int> ans;
    for(int i=0;i<=n-1;i++){
		int low=0, high=n-i, best=-1;
		while(low<=high){
			int mid=(low+high)>>1;
			if(pref[i]+suff[mid]>=l){
				best=mid;
				high=mid-1;
			}
			else low=mid+1;
		}
		
		if(best!=-1 && pref[i]+suff[best]<=u){
			for(int j=n-1;j>=n-best;j--) ans.pb(tr[j].se);
			for(int j=0;j<i;j++) ans.pb(tr[j].se);
			break;
		}
	}
	
	sort(all(ans));
	return ans;
}

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