Submission #252240

#TimeUsernameProblemLanguageResultExecution timeMemory
252240cjoaDetecting Molecules (IOI16_molecules)C++11
100 / 100
67 ms7272 KiB
#include "molecules.h" #include <vector> #include <algorithm> #include <utility> #include <numeric> #include <cassert> #include <cstdio> using namespace std; typedef pair<int,int> II; std::vector<int> find_subset(int l, int u, std::vector<int> w) { if (accumulate(w.begin(), w.end(), 0LL) < l) return {}; const int N = w.size(); vector<II> V; for (int i = 0; i < N; ++i) { V.push_back({w[i], i}); } sort(V.begin(), V.end()); if (V.begin()->first > u) return {}; vector<long long> psum(N+1); for (int i = 1; i <= N; ++i) psum[i] = psum[i-1] + V[i-1].first; // fprintf(stderr, "l:%d u:%d\n", l, u); for (int R = 1; R <= N; ++R) { if (psum[R] < l) continue; int L = lower_bound(psum.begin(), psum.begin()+R, psum[R]-u) - psum.begin(); // fprintf(stderr, "L:%d R:%d psum[R]:%lld\n", L, R, psum[R]); if (psum[R] - psum[L] >= l) { vector<int> res; for (int i = L+1; i <= R; ++i) res.push_back(V[i-1].second); return res; } } return {}; }
#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...