#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 <= M; sum++){
ind[i][sum] = ind[i-1][sum];
if(sum == x){
ind[i][sum] = i;
} else if(sum > x && ind[i][sum] < ind[i-1][sum-x]){
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 |
51 ms |
6516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
182 ms |
13760 KB |
Output is correct |
2 |
Correct |
346 ms |
23628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
596 ms |
50864 KB |
Output is correct |
2 |
Correct |
1061 ms |
75804 KB |
Output is correct |
3 |
Correct |
1090 ms |
85472 KB |
Output is correct |
4 |
Correct |
1503 ms |
111384 KB |
Output is correct |
5 |
Execution timed out |
2075 ms |
172036 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |