Submission #64850

#	Time	Username	Problem	Language	Result	Execution time	Memory
64850		yogahmad	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	102 ms	31624 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 100003
#define pc(x) putchar_unlocked(x);



vector<int> find_subset(int l, int u, vector<int> w) {
	int n=w.size();
	vector<int>ret;
	vector<pair<int,int>>ve;
	for(int i=0;i<n;i++){
		ve.pb({w[i],i});
	}
	sort(ALL(ve));
	long long pref=0,suff=0;
	for(int i=1;i<=n;i++){
		pref=pref+ve[i-1].f;
		suff=suff+ve[n-i].f;
		if(l<=pref && pref<=u){
			for(int j=0;j<i;j++)ret.pb(ve[j].s);
			sort(ALL(ret));
			return ret;
		}
		if(l<=suff && suff<=u){
			for(int j=n-1;j>=n-i;j--){
				ret.pb(ve[j].s);
			}
			sort(ALL(ret));
			return ret;
		}
		if(pref<l && suff>u){
			long long sum=0;
			for(int j=0;j<i;j++){
				sum+=ve[j].f;
			}
			if(l<=sum && sum<=u){
				for(int j=0;j<i;j++){
					ret.pb(ve[j].s);
				}
				sort(ALL(ret));
				return ret;
			}
			for(int j=i;j<n;j++){
				sum+=ve[j].f;
				sum-=ve[j-i].f;
				if(l<=sum && sum<=u){
					for(int k=j-i+1;k<=j;k++){
						ret.pb(ve[k].s);
					}
					return ret;
				}
			}
		}
	}
	return ret;
}

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