Submission #1230357

#TimeUsernameProblemLanguageResultExecution timeMemory
1230357dibamboo23Kpart (eJOI21_kpart)C++20
0 / 100
124 ms992 KiB
#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define sz size()

using namespace std;
[[maybe_unused]]const int e5=1e5;
[[maybe_unused]]const int e6=1e6;
[[maybe_unused]]const int e7=1e7;
[[maybe_unused]]const int e8=1e8;
[[maybe_unused]]const int e9=1e9;

inline int rd(){
	int num;cin>>num;
	return num;
}

inline ll rdll(){
	ll num;cin>>num;
	return num;
}

[[maybe_unused]]const ll inf=1e18+7;
[[maybe_unused]]const ll MOD=1e9+7;
[[maybe_unused]]const int N=1e6+3;

int dp[e5+3];

bool res[N];
int p[N];

int a[1003];

void code(){
	int n;cin>>n;
	for(int i=2;i<=n;i++)res[i]=1;
	for(int j=1;j<=e5;j++)dp[j]=0;
	int k=e5/2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[i]=p[i-1]+a[i];
		dp[a[i]]=i;
		for(int j=k;j>a[i];j--){
			dp[j]=max({dp[j-a[i]],dp[j]});
		}
		for(int j=2;j<=i;j++){
			int l=i-j+1;
			if(((p[i]-p[l-1])&1)==1||dp[(p[i]-p[l-1])/2]<l)res[j]=0;
		}
	}
	vector<int>ress;
	for(int i=1;i<=n;i++){
		if(res[i])ress.push_back(i);
	}
	cout<<(int)ress.sz<<" ";
	for(auto to:ress)cout<<to<<" ";
}




signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--)code(),cout<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...