Submission #415397

#	Time	Username	Problem	Language	Result	Execution time	Memory
415397		jiahng	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	130 ms	23064 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi,ll> pii;
typedef set <ll> si;
typedef vector <int32_t> vi32;
typedef long double ld;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define int ll

vi32 ww;

vi32 find_subset(int32_t l, int32_t u, vi32 w) {
	int N = w.size();
	vi ss, ss2;
	vi i1(N), i2(N);
	iota(all(i1), 0);
	iota(all(i2),0);

	int r = u;
	
	aFOR(i,w) ww.pb(i);
	
	sort(all(i1), [](int i,int j){
		return ww[i] < ww[j];
	});
	sort(all(i2), [](int i,int j){
		return ww[i] > ww[j];
	});

	
    sort(all(w));

    ss.pb(w[0]);
    FOR(i,1,N-1) ss.pb(ss.back() + w[i]);

	reverse(all(w));
	ss2.pb(w[0]);
	FOR(i,1,N-1) ss2.pb(ss2.back() + w[i]);
	//~ return vi32();
	int idx = lbd(ss,l) - ss.begin();
	
	if (idx != N && ss[idx] <= u){
		vi32 ans;
		FOR(i,0,idx) ans.pb(i1[i]);
		return ans;
	}
	idx = lbd(ss2,l) - ss2.begin();
	
	if (idx != N && ss2[idx] <= u){
		vi32 ans;
		//~ cout << idx << '\n';
		FOR(i,0,idx) ans.pb(i2[i]);
		return ans;
	}
	
	idx = ubd(ss,l) - ss.begin() - 1;
	if (idx < 0) return vi32();
	if (ss2[idx] < r) return vi32();

	int sm = ss[idx];
	multiset <pi> cur, out;
	FOR(i,0,idx) cur.insert(pi(ww[i1[i]], i1[i]));
	FOR(i,idx+1,N-1) out.insert(pi(ww[i1[i]], i1[i]));
	
	while (sm < l){
		int x = cur.begin()->f;
		sm -= cur.begin()->f;
		out.insert(*cur.begin());
		cur.erase(cur.begin());
		
		int y = out.rbegin()->f;
		if (y < x) return vi32();
		sm += out.rbegin()->f;
		cur.insert(*out.rbegin());
		out.erase(--out.end());
	}
	
	vi32 ans;
	aFOR(i,cur) ans.pb(i.s);
	return ans;
}

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