#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t, n, s;
cin >> t;
vector<int> a, lasti, pref;
set<int> k;
while (t--){
cin >> n;
a.assign(n+1, 0);
lasti.assign(50001, -1);
pref.assign(n+1, 0);
k.clear();
s = 0;
for (int i=1; i<n+1; i++){
cin >> a[i];
s += a[i];
pref[i] = s;
}
s /= 2;
for (int i=1; i<n+1; i++){
k.insert(i);
for (int j=s-a[i]; j>0; j--){
lasti[j + a[i]] = max(lasti[j + a[i]], lasti[j]);
}
if (a[i] <= s){
lasti[a[i]] = i;
}
auto cur = k.begin();
for (auto it = k.begin(); it != k.end();){
cur = it++;
if ((pref[i] - pref[i - *cur]) % 2 || lasti[(pref[i] - pref[i - *cur]) / 2] < i - *cur + 1){
k.erase(cur);
}
}
}
cout << k.size() << " ";
for (int x : k){
cout << x << " ";
}
cout << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
468 KB |
Output is correct |
2 |
Correct |
40 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
152 ms |
544 KB |
Output is correct |
2 |
Correct |
363 ms |
528 KB |
Output is correct |
3 |
Correct |
415 ms |
552 KB |
Output is correct |
4 |
Correct |
686 ms |
552 KB |
Output is correct |
5 |
Correct |
1602 ms |
564 KB |
Output is correct |
6 |
Execution timed out |
2070 ms |
712 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |