#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define count1(x) __builtin_popcount(x)
#define endl '\n'
using namespace std;
const int N = 2e5+1, mod = 1e6, M = 5e4;
inline void test_case(){
int n;
cin >> n;
vector<int>pre(n+1, 0), ans;
vector<vector<int>> ind(n+1, vector<int>(M+1, 0));
for(int i = 1; i <= n; i++){
int x;
cin >> x;
pre[i] = pre[i-1] + x;
for(int sum = 0; sum < x; sum++){
ind[i][sum] = ind[i-1][sum];
}
ind[i][x] = i;
for(int sum = x+1; sum <= M; sum++){
ind[i][sum] = ind[i-1][sum];
ind[i][sum] = max(ind[i][sum], ind[i-1][sum-x]);
}
}
for(int k = 1; k <= n; k++){
bool ok = true;
for(int l = 1; l+k-1 <= n; l++){
int r = l+k-1;
int sum = pre[r] - pre[l-1];
if(sum % 2 != 0 || ind[r][sum/2] < l){
ok = false;
break;
}
}
if(ok){
ans.pb(k);
}
}
cout << ans.size() << " ";
for(auto x : ans){
cout << x << " ";
}
cout << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while(T--){
test_case();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
6516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
146 ms |
13752 KB |
Output is correct |
2 |
Correct |
286 ms |
23632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
553 ms |
50936 KB |
Output is correct |
2 |
Correct |
970 ms |
75688 KB |
Output is correct |
3 |
Correct |
986 ms |
85632 KB |
Output is correct |
4 |
Correct |
1391 ms |
111292 KB |
Output is correct |
5 |
Execution timed out |
2041 ms |
171936 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |