#include <bits/stdc++.h>
#define pb push_back
#pragma GCC target("avx2,bmi,bmi2")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
vector<vector<short>> dp(1001,vector<short>(50002,-1));
int n;
cin >> n;
vector<int> v(n),pref(n+1,0);
for(auto&i:v)cin>>i;
for(int i = 0; i < n; i++){
pref[i+1]=pref[i]+v[i];
dp[i+1][v[i]]=i+1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= pref[i]; j++){
dp[i][j]=max({dp[i][j],dp[i-1][j]});
if(v[i-1]<j){
dp[i][j] = max(dp[i][j], dp[i-1][j-v[i-1]]);
}
}
}
vector<int> ans;
for(int i = 1; i <= n; i++){
bool ok=1;
for(int j = i; j <= n; j++){
int sum=pref[j]-pref[j-i];
if(sum&1){
ok=0;break;
}
if(dp[j][sum/2] < (j-i+1)){
ok=0;break;
}
}
if(ok) ans.pb(i);
}
cout << ans.size() << ' ';
for(auto i : ans) cout << i << ' ';
cout << '\n';
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |