Submission #253206

#	Time	Username	Problem	Language	Result	Execution time	Memory
253206		nandonathaniel	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	68 ms	5624 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

pii arr[200000];

vector<int> find_subset(int l, int u, vector<int> w) {
    int n=w.size();
    for(int i=0;i<n;i++)arr[i]={w[i],i};
    sort(arr,arr+n);
    int ptr=0;
    long long tot=0;
    vector<int> ans;
    for(int i=0;i<n;i++){
		while(ptr<n && tot<l){
			tot+=arr[ptr].first;
			ptr++;
		}
		if(tot>=l && tot<=u){
			for(int j=i;j<ptr;j++)ans.push_back(arr[j].second);
			break;
		}
		tot-=arr[i].first;
	}
	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