Submission #419040

#	Time	Username	Problem	Language	Result	Execution time	Memory
419040		Blagojce	Detecting Molecules (IOI16_molecules)	C++11	69 / 100	1039 ms	5444 KiB

molecules

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 1e5+5;

#include "molecules.h"

std::vector<int> find_subset(int l, int r, std::vector<int> w){
	if(l == 0) return std::vector<int>(0);
	vector<pii> v;
	int n = (int)w.size();
	fr(i, 0, n) v.pb({w[i], i});
	sort(all(v));
	
	fr(i, 0, n){
		ll s = 0;
		vector<int> pot;
		fr(j, i, n){
			pot.pb(v[j].nd);
			s += v[j].st;
			if(l <= s && s <= r){
				return pot;
			}
		}
	}
	return std::vector<int>(0);
	
	/*int n = (int)w.size();
	sort(all(w));
	int lp = 0;
	int rp = 0;
	ll sum = 0;
	while(rp < n && sum < l){
		sum += w[rp++];
		while(lp < rp && sum > r){
			sum -= w[lp++];
		}
	}
	if(l <= sum && sum <= r){
		vector<int> sol;
		while(lp < rp) sol.pb(lp++);
		return sol;
	}
		
	
	return std::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: 0 / 31