Submission #255812

#	Time	Username	Problem	Language	Result	Execution time	Memory
255812		jainbot27	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	384 KiB

molecules

#include <bits/stdc++.h>
#include <molecules.h>
using namespace std;
using ll = long long; 
// u - l >= wmax - wmin
// what does this mean for me
vector<int> find_subset(int l, int u, vector<int> w){
	int n=w.size();
	sort(w.begin(), w.end());
	assert(*(w.rbegin()) - *(w.begin()) <= u - l);
	vector<int> ret;
	if(u < w[0]){
		return ret;
	}
	ll sum = 0;
	for(int i = n-1; i >= 1; i--){
		sum += w[i];
		if(sum > u){
			sum -= w[i];
			sum += w[0];
			if(sum >= l && sum <= u){
				for(int j = n-1; j > i; j--){
					ret.push_back(j);
				}
				ret.push_back(0);
				return ret;
			}
		}
		else if(sum >= l){
			for(int j = n-1; j >= i; j--){
				ret.push_back(j);
			}
			return ret;
		}
	}
	sum += w[0];
	if(sum >= l && sum <= u){
		for(int i =0; i < n; i++){
			ret.push_back(i);
		}
		return ret;
	}
	else{
		return ret;
	}
}

// int main(){
// 	int l = 10;
// 	int u = 20;
// 	vector<int> w = {15, 17, 16, 18};
// 	vector<int> ret = find_subset(l, u, w);
// 	for(int x : ret){
// 		cout << x << " ";
// 	}
// 	cout << endl;
// }

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