Submission #388548

#	Time	Username	Problem	Language	Result	Execution time	Memory
388548		alireza_kaviani	Detecting Molecules (IOI16_molecules)	C++11	0 / 100	1 ms	204 KiB

molecules

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

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

#define X		first
#define Y		second
#define sep		' '
#define all(x)	(x).begin() , (x).end()
#define SZ(x)	int(x.size())

vector<int> find_subset(int l, int u, vector<int> w) {
	vector<pii> vec;
	vector<int> ans1 , ans2;
	int n = SZ(w) ; ll sum = 0;
	for(int i = 0 ; i < n ; i++){
		vec.push_back({w[i] , i});
	}
	sort(all(vec));
	for(pii i : vec){
		sum += i.X;
		ans1.push_back(i.Y);
		if(sum >= l)	break;
	}
	if(sum <= u){
		sort(all(ans1));
		return ans1;
	}
	sum -= w[ans1.back()]; ans1.pop_back();
	while(SZ(ans1)){
		sum -= w[ans1.back()]; ans1.pop_back(); n--;
		sum += w[vec[n].Y]; ans2.push_back(vec[n].Y);
		if(l <= sum){
			for(int i : ans2)	ans1.push_back(i);
			sort(all(ans1));
			return ans1;
		}
	}
    return vector<int>();
}

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