Submission #1015021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015021		ziyad_alharbi	Detecting Molecules (IOI16_molecules)	C++14	31 / 100	135 ms	65536 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
int n;
int L, R, sf[200005];
pair<int, int>wh[200005];
bool b;
set<int>g[200005];
set<int>st;
void f(int x, int s)
{
	//cout << x << ' ';
	if (s >= L && !b)
	{
		b = 1;
		return;
	}
	if (x == n || b || wh[x].first + s > R || s + sf[x] < L || g[x].count(s))return;
	//cout << x << ' ' << s << '\n';
	st.insert(wh[x].second);
	f(x + 1, s + wh[x].first);
	if (b)return;
	st.erase(wh[x].second);
	f(x + 1, s);
	g[x].insert(s);
}
vector<int> find_subset(int l, int u, vector<int> w)
{
	n = w.size();
	long long s = 0;
	for (int x = 0; x < n; x++)
	{
		wh[x].first = w[x];
		wh[x].second = x;
	}
	for (int x = n - 1; x >= 0; x--)
	{
		sf[x] = w[x];
		if (x != n - 1)sf[x] += sf[x + 1];
	}
	sort(wh, wh + n);
	L = l;
	R = u;
	if (s >= L && s <= R)
	{
		vector<int>a;
		for (int x = 0; x < n; x++)
		{
			a.push_back(x);
		}
		return a;
	}
	f(0, 0);
	if (st.size())
	{
		vector<int>a;
		for (auto i : st)
		{
			a.push_back(i);
		}
		return a;
	}
	else
	{
		return vector<int>(0);
	}
 
}
/*signed main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	int t = 1;
	//cin>>t;
	while (t--)
	{
		int N, L, R;
		cin >> N >> L >> R;
		vector<int> w(N);
		for (int x = 0; x < N; x++)
		{
			cin >> w[x];
		}
		vector<int>a = find_subset(L, R, w);
		int nh = a.size();
		for (int x = 0; x < nh; x++)cout << a[x] << ' ';
	}
	return 0;
}*/

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