# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
151544 | 2019-09-03T14:11:16 Z | mhy908 | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KB |
#include "molecules.h" #include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long LL; int N; int A[MAXN]; LL S[MAXN]; vector<int> find_subset(int l, int u, vector<int> w) { int t = 0; N = sz(w); for (int i=1;i<=N;i++) A[i] = i; sort(A+1, A+N+1, [&w](const int &a, const int &b){ return w[a-1] < w[b-1]; }); for (int i=1;i<=N;i++) S[i] = S[i-1] + w[A[i]-1]; for (int i=1;i<=N;i++){ LL p = S[i]; LL q = S[N]-S[N-i]; if (p <= u && q >= l){ t = i; break; } } vector <int> ret; if (!t) return ret; for (int i=t;i<=N;i++){ lld v = S[i] - S[i-t]; if (v < l || v > u) continue; for (int j=0;j<t;j++) ret.pb(A[i-j]-1); break; } return ret; }