Submission #787366

#	Time	Username	Problem	Language	Result	Execution time	Memory
787366		Sohsoh84	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	45 ms	8096 KiB

molecules

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

using namespace std;

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

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

ll n, l, u;
vector<pll> vec;
vector<ll> W;

inline vector<int> get(vector<int> t) {
	vector<int> ans;
	for (int e : t)
		ans.push_back(vec[e].Y);

	sort(all(ans));
	return ans;
}

inline bool good(ll x) {
	return x >= l && x <= u;
}

vector<int> find_subset(int l_, int u_, vector<int> w_) {
	l = l_, u = u_;
	set<pll> st;
	n = w_.size();
	for (int i = 0; i < n; i++)
		vec.push_back({w_[i], i});	

	sort(all(vec));
	for (int i = 0; i < n; i++)
		W.push_back(vec[i].X);

	ll mn_s = 0, mx_s = 0;
	vector<int> mn_vec;
	for (int i = 0; i < n; i++) {
		mn_s += W[i], mx_s += W[n - i - 1];
		mn_vec.push_back(i);
		if (!good(mn_s) && !good(mx_s) && !(mn_s < l && mx_s > u)) continue;
	
		int ind = n - 1;
		vector<int> tmn;
		while (!good(mn_s)) {
			mn_s -= W[mn_vec.back()];
			mn_vec.pop_back();
			tmn.push_back(ind--);
			mn_s += W[tmn.back()];
		}

		for (int e : tmn)
			mn_vec.push_back(e);
	
		return get(mn_vec);
	}


	return vector<int>(0);
}

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