Submission #600236

#	Time	Username	Problem	Language	Result	Execution time	Memory
600236		Fidan	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	67 ms	7452 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
vector<int> find_subset(int l, int u, vector<int> w1) {
	
	vector<ll> cvb;
	
	ll n=w1.size(), i, c1=-1, c2=-1;
	vector<pair<ll, ll>> w;
	
	w.push_back({0, 0});
	
	for(i=0; i<n; i++){
		w.push_back({w1[i], i+1});
	}
	
	sort(w.begin(), w.end());
	
	vector<ll> v(n+1, 0);
	for(i=1; i<=n; i++){
		v[i]=v[i-1]+w[i].first;
	}
	
	for(i=1; i<=n; i++){
		ll lo=i, hi=n;
		while(lo<=hi){
			ll mid=(lo+hi)/2;
			if(v[mid]-v[i-1]<l) lo=mid+1;
			else if(v[mid]-v[i-1]>u) hi=mid-1;
			else {
				c1=i, c2=mid;
				break;
			}
		}
	}
	
	if(c1==-1) return cvb;
	
	for(i=c1; i<=c2; i++){
		cvb.push_back(w[i].second-1);
	}
	return cvb;
}

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