Submission #66122

#	Time	Username	Problem	Language	Result	Execution time	Memory
66122		gnoor	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	93 ms	13784 KiB

molecules

#include "molecules.h"

#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

bool check(long long l,long long u,long long val) {
	return val>=l&&val<=u;
}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	int n=w.size();
	vector<pair<int,int>> tbl(n);
	vector<long long> qsl(n);
	vector<long long> qsr(n);
	for (int i=0;i<n;i++) {
		tbl[i]={w[i],i};
	}
	sort(tbl.begin(),tbl.end());
	for (int i=0;i<n;i++) {
		qsl[i]=tbl[i].first;
		if (i) qsl[i]+=qsl[i-1];
	}
	for (int i=n-1;i>=0;i--) {
		qsr[i]=tbl[i].first;
		if (i<n-1) qsr[i]+=qsr[i+1];
	}
	vector<int> ans;
	long long ll;
	long long rr;
	for (int i=1;i<=n;i++) {
		if (qsr[n-i]<l) continue;
		if (qsl[i-1]>u) continue;
		for (int j=0;j<=i;j++) {
			ll=j?qsl[j-1]:0;
			rr=(j==i)?0:qsr[n-i+j];
			if (check(l,u,ll+rr)) {
				for (int k=0;k<j;k++) {
					ans.push_back(tbl[k].second);
				}
				for (int k=0;k<i-j;k++) {
					ans.push_back(tbl[n-k-1].second);
				}
				return ans;
			}
		}
		assert(false);
	}
    return std::vector<int>(0);
}

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