Submission #833438

#	Time	Username	Problem	Language	Result	Execution time	Memory
833438		iskhakkutbilim	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	212 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;
#define ff first
#define ss second
/*
4
6 8 8 7
15 17
*/

/*
4
5 5 6 6
14 15
*/

/*
4
15 17 16 18
10 20
*/

/*
4
1 10 5 4
20 21
*/
vector<int> find_subset(int l, int u, vector<int> w){
	vector<int> ans;
	int n = w.size();
	vector<pair<int ,int>> a;
	int sum = 0;
	for(int i = 0;i < n; i++){
		a.push_back({w[i], i});
	}
	sort(a.begin(), a.end());
	set<pair<int, int> > st;
	for(int i = 0;i < n; i++){
		auto [x, idx] = a[i];
		sum+= x;
		if(sum >= l and sum <= u){
			for(int j = 0;j <= i; j++){
				ans.push_back(a[j].ss);
			}
			return ans;
		}else if(sum > u){
			int left = sum - u, right = sum - l;
			auto it = st.lower_bound({left, -1});
			if(it == st.end() or it->ff > right or it->ff < l){
				continue;
			}
			it++;
			while(it != st.end()){
				int j = it->ss;
				ans.push_back(a[j].ss);
				it++;
			}
			ans.push_back(a[i].ss);
			return ans;
		}
		st.insert({sum, i});
	}
	return ans;
}


//main(){
//	int n; cin >> n;
//	vector<int> w(n);
//	for(int i = 0;i < n; i++){
//		cin >> w[i];
//	}
//	int l, u; cin >> l >> u;
//	vector<int> index = find_subset(l, u, w);
//	for(auto j : index){
//		cout << j << ' ';
//	}
//}

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