Submission #151319

#	Time	Username	Problem	Language	Result	Execution time	Memory
151319		youssefbou62	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	85 ms	7916 KiB

molecules

//#include "molecules.h"
#include  <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab  (int  x ) { return (x>0?x:-x); }

ll sum(int l , int r ,vector<ll>& p){
	if( l== 0) return p[r] ; 
	return p[r]-p[l-1] ;
}

bool in(ll x , ll l , ll r){
	return ( x >= l && x <= r ) ;
}
vector<int> find_subset(int l, int u, vector<int> w) {
    vector<int> result ; 
    int n = w.size() ; 
    vector<ll>pref(n);
    // sort(all(w));
    vpi cost; 
    for(int i =0 ; i < n ; i++ )cost.pb({w[i],i}); 
    sort(all(cost)); 
    pref[0]=cost[0].fi ; 
    for(int i = 1 ; i < n ; i++ )pref[i] += pref[i-1] + 1LL*cost[i].fi ;
    for(int i = 0 ; i < n ; i++ ){
    	int L = i , r = n-1 ; 
    	while ( L <= r){
    		int mid=(L+r)/2 ; 
    		if( in(sum (i,mid,pref),l,u) ){
    			// cout << sum(i,mid,pref)<<endl;
    			for(int j = i ; j <= mid ; j++ )result.pb(cost[j].se) ; 
    			sort(all(result));
    			return result ; 
    		}
    		if( sum(i,mid,pref) < l )L = mid+1; 
    		if( sum(i,mid,pref)>u)r = mid-1 ;
    	}
    }
    return result; 
}
// int main(){
// 	vector<int> v = find_subset(15, 17, {6, 8, 8, 7});
// 	for(int i : v )cout << i << " " ; cout << endl; 
// 	v= find_subset(14, 15, {5, 5, 6, 6});  
// 	for(int i : v )cout << i << " " ; cout << endl; 
// 		v = find_subset(10, 20, {15, 17, 16, 18}); 
// 	for(int i : v )cout << i << " "; 
// }

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