#include<bits/stdc++.h>
//#include "molecules.h"
using namespace std;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
std::vector<int> find_subset(int l, int u, std::vector<int> w){
pair<int,int> par[u+1];
int n=w.size();
bitset<500005> dp;
for (int i = 0; i <= u; ++i)
{
par[i]={n,i};
}
dp[0]=1;
bool vis[u+1];
vis[0]=true;
memset(vis,0,sizeof vis);
bitset<500005> nabba;
for (int i = 1; i <= n; ++i)
{
int cur=w[i-1];
nabba=(dp^(dp|(dp<<cur)));
dp|=(dp<<cur);
for (int j = nabba._Find_first(); j < nabba.size(); j=nabba._Find_next(j))
{
par[j]={i-1,j-cur};
}
/*for (int j = 1; j <= u; ++j)
{
if(dp[j]==1&&vis[j]==0){
par[j]={i-1,j-cur};
vis[j]=true;
}
}*/
}
vector<int> ans;
/*for (int i = 0; i <= u; ++i)
{
cout <<par[i].se<<" ";
}cout <<endl;*/
for (int i = l; i <= u; ++i)
{
if(dp[i]){
while(i>0){
//cout <<i<<endl;
ans.pb(par[i].fi);
i=par[i].se;
//break;
}
break;
}
}
sort(ans.begin(),ans.end());
return ans;
}
/*int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, l, u;
assert(3 == scanf("%d %d %d", &n, &l, &u));
std::vector<int> w(n);
for (int i = 0; i < n; i++)
assert(1 == scanf("%d", &w[i]));
std::vector<int> result = find_subset(l, u, w);
printf("%d\n", (int)result.size());
for (int i = 0; i < (int)result.size(); i++)
printf("%d%c", result[i], " \n"[i == (int)result.size() - 1]);
}*/
Compilation message
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:29:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int j = nabba._Find_first(); j < nabba.size(); j=nabba._Find_next(j))
| ~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
1 ms |
600 KB |
OK (n = 1, answer = NO) |
3 |
Correct |
0 ms |
604 KB |
OK (n = 1, answer = YES) |
4 |
Correct |
1 ms |
604 KB |
OK (n = 2, answer = YES) |
5 |
Correct |
1 ms |
600 KB |
OK (n = 2, answer = YES) |
6 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
7 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
8 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
9 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
10 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
11 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
12 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
13 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
1 ms |
600 KB |
OK (n = 1, answer = NO) |
3 |
Correct |
0 ms |
604 KB |
OK (n = 1, answer = YES) |
4 |
Correct |
1 ms |
604 KB |
OK (n = 2, answer = YES) |
5 |
Correct |
1 ms |
600 KB |
OK (n = 2, answer = YES) |
6 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
7 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
8 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
9 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
10 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
11 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
12 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
13 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
1 ms |
600 KB |
OK (n = 1, answer = NO) |
3 |
Correct |
0 ms |
604 KB |
OK (n = 1, answer = YES) |
4 |
Correct |
1 ms |
604 KB |
OK (n = 2, answer = YES) |
5 |
Correct |
1 ms |
600 KB |
OK (n = 2, answer = YES) |
6 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
7 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
8 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
9 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
10 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
11 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
12 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
13 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
1 ms |
600 KB |
OK (n = 1, answer = NO) |
3 |
Correct |
0 ms |
604 KB |
OK (n = 1, answer = YES) |
4 |
Correct |
1 ms |
604 KB |
OK (n = 2, answer = YES) |
5 |
Correct |
1 ms |
600 KB |
OK (n = 2, answer = YES) |
6 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
7 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
8 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
9 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
10 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
11 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
12 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
13 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
OK (n = 1, answer = NO) |
2 |
Correct |
1 ms |
600 KB |
OK (n = 1, answer = NO) |
3 |
Correct |
0 ms |
604 KB |
OK (n = 1, answer = YES) |
4 |
Correct |
1 ms |
604 KB |
OK (n = 2, answer = YES) |
5 |
Correct |
1 ms |
600 KB |
OK (n = 2, answer = YES) |
6 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
7 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
8 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
9 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
10 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
11 |
Correct |
1 ms |
604 KB |
OK (n = 3, answer = YES) |
12 |
Correct |
1 ms |
600 KB |
OK (n = 3, answer = YES) |
13 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |