#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
long long n, lower, upper;
vector<pair<long long, long long> > store;
long long pf[200001];
void pfcompute() {
pf[0] = store[0].first;
for (long long i=1; i<n; i++) {
pf[i] = pf[i-1] + store[i].first;
}
}
long long pfquery(long long a, long long b) {
if (a == 0) return pf[b];
return pf[b] - pf[a-1];
}
pair<long long, long long> solve_for(long long left) {
//
long long low = left;
long long high = n;
long long mid;
while (low + 1 < high) {
mid = (low + high) / 2;
long long sumr = pfquery(left, mid);
if (sumr > upper) {
high = mid;
}
else if (sumr < lower) {
low = mid;
}
else {
return make_pair(left, mid);
}
}
if (pfquery(mid, mid) <= upper && pfquery(mid, mid) >= lower) {
return make_pair(mid, mid);
}
if (pfquery(mid, low) <= upper && pfquery(mid, low) >= lower) {
return make_pair(mid, low);
}
if (high != n) {
if (pfquery(mid, high) <= upper && pfquery(mid, high) >= lower) {
return make_pair(mid, high);
}
}
return make_pair(-1, -1);
}
vector<int> find_subset(int l, int u, vector<int> w) {
//
n = w.size();
lower = l;
upper = u;
for (long long i=0; i<n; i++) {
store.push_back(make_pair(w[i], i));
}
sort(store.begin(), store.end());
/*for (int i=0; i<n; i++) {
cout << store[i].first << ":" << store[i].second << endl;
}*/
pfcompute();
vector<int> ind;
for (long long leftlock=0; leftlock<n; leftlock++) {
pair<long long, long long> res = solve_for(leftlock);
if (res.first == -1 && res.second == -1) {
continue;
}
else {
for (long long i=res.first; i<=res.second; i++) {
ind.push_back(store[i].second);
}
return ind;
}
}
return ind;
}
Compilation message
molecules.cpp: In function 'std::pair<long long int, long long int> solve_for(long long int)':
molecules.cpp:17:5: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (a == 0) return pf[b];
^~
molecules.cpp:25:15: note: 'mid' was declared here
long long mid;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
3 |
Incorrect |
2 ms |
384 KB |
Contestant can not find answer, jury can |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
OK (n = 12, answer = YES) |
2 |
Correct |
2 ms |
384 KB |
OK (n = 12, answer = YES) |
3 |
Correct |
2 ms |
384 KB |
OK (n = 12, answer = NO) |
4 |
Correct |
2 ms |
256 KB |
OK (n = 12, answer = NO) |
5 |
Correct |
2 ms |
384 KB |
OK (n = 12, answer = YES) |
6 |
Correct |
2 ms |
384 KB |
OK (n = 12, answer = YES) |
7 |
Correct |
2 ms |
384 KB |
OK (n = 12, answer = YES) |
8 |
Correct |
2 ms |
384 KB |
OK (n = 12, answer = YES) |
9 |
Correct |
2 ms |
256 KB |
OK (n = 6, answer = YES) |
10 |
Correct |
2 ms |
384 KB |
OK (n = 12, answer = YES) |
11 |
Correct |
2 ms |
384 KB |
OK (n = 100, answer = NO) |
12 |
Correct |
2 ms |
384 KB |
OK (n = 100, answer = YES) |
13 |
Correct |
2 ms |
384 KB |
OK (n = 100, answer = NO) |
14 |
Correct |
2 ms |
384 KB |
OK (n = 100, answer = YES) |
15 |
Correct |
3 ms |
384 KB |
OK (n = 100, answer = YES) |
16 |
Correct |
2 ms |
384 KB |
OK (n = 100, answer = YES) |
17 |
Correct |
2 ms |
384 KB |
OK (n = 100, answer = YES) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
3 |
Incorrect |
2 ms |
384 KB |
Contestant can not find answer, jury can |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
3 |
Incorrect |
2 ms |
384 KB |
Contestant can not find answer, jury can |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
3 |
Incorrect |
2 ms |
384 KB |
Contestant can not find answer, jury can |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
2 ms |
384 KB |
OK (n = 1, answer = NO) |
3 |
Incorrect |
2 ms |
384 KB |
Contestant can not find answer, jury can |
4 |
Halted |
0 ms |
0 KB |
- |