# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
237050 | 2020-06-04T10:28:48 Z | michao | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "molecules.h" #define ll long long int #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; vi find_subset(int l,int u,vi w) { vector<pii>tab; int n=sz(w); tab.clear(); int licznik=1; for (auto it:w)tab.pb(mp(it,licznik)),licznik++; sort(tab.begin(),tab.end()); vi ans; ans.clear(); int wskl=-1,wskr=-1; vector<ll> pref; pref.clear(); ll sum=0; for (int i=0;i<n;i++)sum+=tab[i].st,pref.pb(sum); for (int i=0;i<sz(pref);i++) { if (pref[i]>=l && pref[i]<=u) { wskl=0,wskr=i; break; } } for (int i=1;i<sz(pref);i++) { for (int j=i;j<sz(pref);j++) { if (pref[j]-pref[i-1]>=l && pref[j]-pref[i-1]<=u) { wskl=i,wskj=r; break; } } if (wskl!=-1) break; } if (wskl!=-1)for (int i=wskl;i<=wskr;i++)ans.pb(tab[i].nd); return ans; } /* int32_t main() { BOOST; vi rak; rak=find_subset(10, 20, {15, 17, 16, 18}); cout<<sz(rak)<<"\n"; for (auto it:rak)cout<<it<<" "; return 0; } */