#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t, n, s, sum, op;
cin >> t;
while (t--){
cin >> n;
int a[n + 1];
bool k[n + 1];
s = a[0] = k[0] = 0;
for (int i=1; i<n+1; i++){
cin >> a[i];
s += a[i];
k[i] = true;
}
s /= 2;
int lasti[s + 1] = {};
for (int i=1; i<n+1; 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;
}
sum = 0;
for (int j=i; j>0; j--){
sum += a[j];
if (sum % 2 || lasti[sum / 2] < j){
k[i - j + 1] = false;
}
}
}
op = 0;
for (int x : k){
if (x){
op++;
}
}
cout << op << " ";
for (int i=1; i<n+1; i++){
if (k[i]){
cout << i << " ";
}
}
cout << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
10 ms |
352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
368 KB |
Output is correct |
2 |
Correct |
109 ms |
412 KB |
Output is correct |
3 |
Correct |
133 ms |
340 KB |
Output is correct |
4 |
Correct |
225 ms |
464 KB |
Output is correct |
5 |
Correct |
503 ms |
564 KB |
Output is correct |
6 |
Correct |
720 ms |
660 KB |
Output is correct |
7 |
Correct |
664 ms |
584 KB |
Output is correct |