Submission #761496

#	Time	Username	Problem	Language	Result	Execution time	Memory
761496		midi	Detecting Molecules (IOI16_molecules)	C++14	9 / 100	1 ms	352 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
	
typedef long long ll;
typedef vector<ll> vcll;
typedef pair<ll, ll> prll;
	
#define f0r(i, a, n) for (i = a; i < n; i++)
#define f1r(i, a, n) for (i = a; i <= n; i++)
#define r0f(i, n, a) for (i = n; i > a; i--)
#define r1f(i, n, a) for (i = n; i >= a; i--)
	
#define pb push_back
#define all(item) item.begin(), item.end()
	
#define mxN 200'000
#define INF (LLONG_MAX >> 2)
	
ll n;
vector<int> ar;
	
unordered_map<int, vcll> indeces;

inline void build_indeces()
{
	ll i;
	f0r(i, 0, n)
		indeces[ar[i]].pb(i);
}

inline bool have_union(ll l1, ll r1, ll l2, ll r2)
{
	return !(r1 < l2 || r2 < l1);
}

vector<int> ans;

inline void ans_push(ll i)
{
	ans.pb(indeces[ar[i]].back());
	indeces[ar[i]].pop_back();
}

inline vector<int> &correct_subset(ll ls, ll rs, ll i1, ll i2, ll l, ll u)
{
	// printf("ls: %lli, rs: %lli\n", ls, rs);
	// printf("l: %lli, u: %lli\n", l, u);
	ll i;

	if (l <= ls)
	{
		// printf("first\n");
		f1r(i, 0, i1)
			ans_push(i);
		sort(all(ans));
		return ans;
	}
	if (u >= rs)
	{
		// printf("second\n");
		r1f(i, n-1, i2)
			ans_push(i);
		sort(all(ans));
		return ans;
	}
	
	ll ri = n - 1;

	// printf("otherwise\n");
	for (; i1 >= 0; i1--)
	{
		ls += ar[ri] - ar[i1];
		ans_push(ri);
		if (ls >= l) break;
	}

	for (; i1 >= 0; i1--)
		ans_push(i1);

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

vector<int> find_subset(int l, int u, vector<int> w)
{
	// printf("l: %i, u: %i\n", l, u);
	n = w.size();
	ar.swap(w);
	
	build_indeces();
	sort(all(ar));
	
	ll i;
	ll ls = 0, rs = 0;
	
	f0r(i, 0, n)
	{
		if (have_union(ls, rs, l, u))
		{
			return correct_subset(ls, rs, i - 1, n - i, l, u);
		}

		ls += ar[i];
		rs += ar[n - i - 1];
	}
	
	if (have_union(ls, rs, l, u)) return correct_subset(ls, rs, n - 1, 0, l, u);
	
	// printf("nothing gg\n");
	return ans;
}

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