제출 #518828

#제출 시각아이디문제언어결과실행 시간메모리
518828GiantpizzaheadDetecting Molecules (IOI16_molecules)C++17
0 / 100
1 ms336 KiB
/* Solution: Sort the weights, and take all of the largest ones until the sum >= l. To check if it's possible, take the same # of elements, but all the smallest ones now. If the smallest sum <= u, then it's possible. Now, start with all the largest weights, and move one at a time down to the smallest ones. You'll step by no more than w_max - w_min, which means you'll step no more than u-l, so you'll hit the target range eventually. Runtime: O(N * log(N)) */ #include "molecules.h" #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); i++) #define sz(x) ((int) x.size()) #define all(x) x.begin(), x.end() #define debug if (true) cerr using ll = long long; int N, K; ll L, U; struct Pair { int w, id; }; vector<Pair> W; vector<bool> used; ll currSum; void use(int i) { used[i] = true; currSum += W[i].w; } void drop(int i) { used[i] = false; currSum -= W[i].w; } vector<int> find_subset(int l, int u, vector<int> w) { vector<int> ans; N = sz(w), L = l, U = u; used.resize(N); rep(i, 0, N) W.push_back({w[i], i}); sort(all(W), [](const Pair& a, const Pair& b) { return a.w < b.w; }); // Use K largest K = 0, currSum = 0; while (true) { use(N-1-K); K++; if (currSum >= L) break; } if (currSum < L) return ans; // Use K smallest ll minSum = 0; rep(i, 0, K) minSum += W[i].w; if (minSum > U) return ans; // Answer exists in between these rep(i, 0, K+1) { if (currSum >= L && currSum <= U) { // This works rep(j, 0, N) if (used[j]) ans.push_back(j); return ans; } if (i == K) break; drop(N-1-i); use(i); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...