# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
129788 | 2019-07-13T08:49:00 Z | miguel | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include <molecules.h> using namespace std; #define rc(x) return cout<<x<<endl,0 #define pb push_back #define dbg(x) cout << #x << '=' << x << '\n'; #define ll long long #define int ll #define sz size() #define x first #define y second #define pi pair <int, int> #define pii pair <int, pi> #define vi vector <int> const ll mod = 1e9 + 7; vi find_subset(int l, int u, vi w){ vector<pi> v; v.pb({0, 0}); int n=w.size(); for(int i=0; i<w.size(); i++) v.pb({w[i], i+1}); sort(v.begin(), v.end()); int s[200002]; s[0]=0; for(int i=1; i<=n; i++) s[i]=s[i-1]+v[i].x; int k=0; while(s[k+1]-s[1]<l && s[n]-s[n-k]<l){k++;} if(k==0) return {}; for(int i=1; i<=n-k+1; i++){ if(s[i+k-1]-s[i-1]>=l && s[i+k-1]-s[i-1]<=u){ vector <int> ans; for(int j=i; j<=i+k-1; j++) ans.pb(v[j].y); return ans; } } return {}; }