Submission #139529

#	Time	Username	Problem	Language	Result	Execution time	Memory
139529		cfalas	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	72 ms	8928 KiB

molecules

#include<bits/stdc++.h>
using namespace std;
#include "molecules.h"
#define ll long long
typedef pair<ll, ll> ii;
#define S second
#define F first

std::vector<int> find_subset(int p, int u, std::vector<int> w) {
	vector<ii> a;
	ll n = w.size();
	for(ll i=0;i<n;i++) a.push_back(ii(w[i], i));
	sort(a.begin(), a.end());
	ll su[n];
	su[0] = a[0].F;
	for(ll i=1;i<n;i++) su[i] = su[i-1] + a[i].F;
	//for(ll i=0;i<n;i++) cout<<su[i]<<" ";
	//cout<<endl;
	for(ll l=0;l<n;l++){
		// -su[l-1] + su[r] >= p
		// su[r] >= su[l-1] + p
		ll r;
		if(l==0) r = lower_bound(su+l, su+n, p) - su; 
		else r = lower_bound(su+l, su+n, su[l-1] + p) - su; 
		//cout<<l<<" "<<r<<" "<<su[r]<<" "<<su[l-1]<<" "<<endl;
		if(l!=0 && su[r]-su[l-1]>=p && su[r]-su[l-1]<=u || l==0 && su[r]>=p && su[r]<=u){
			vector<int> ans;
			for(ll i=l;i<=r;i++) ans.push_back(a[i].S);
			return ans;
		}
	}
	return vector<int>();
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:26:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(l!=0 && su[r]-su[l-1]>=p && su[r]-su[l-1]<=u || l==0 && su[r]>=p && su[r]<=u){
      ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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