This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int logn=25;
/* LazySeg tree
int n;
int st[4*maxn];///min
int lz[4*maxn];
void u(int L,int R,int i,int j,int nval,int pos)
{
if(lz[pos]!=0)
{
st[pos]+=lz[pos];
if(L!=R)
{
lz[2*pos]+=lz[pos];
lz[2*pos+1]+=lz[pos];
}
lz[pos]=0;
}
if(i<=L && R<=j)
{
st[pos]+=nval;
if(L!=R)
{
lz[2*pos]+=nval;
lz[2*pos+1]+=nval;
}
return ;
}
if(R<i || L>j)
{
return;
}
int mid=(L+R)/2;
u(L,mid,i,j,nval,2*pos);
u(mid+1,R,i,j,nval,2*pos+1);
st[pos]=min(st[2*pos],st[2*pos+1]);
}
int query(int L,int R,int i,int j,int pos)
{
if(lz[pos]!=0)
{
st[pos]+=lz[pos];
if(L!=R)
{
lz[2*pos]+=lz[pos];
lz[2*pos+1]+=lz[pos];
}
lz[pos]=0;
}
if(i<=L && R<=j)
{
return st[pos];
}
if(R<i || L>j)
{
return 1e15;
}
int mid=(L+R)/2;
return min(query(L,mid,i,j,2*pos),query(mid+1,R,i,j,2*pos+1));
}*/
signed main()
{
///freopen("sirbun.in","r",stdin);
///freopen("sirbun.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
int n;
while(t--)
{
cin>>n;
int x[n+1];
int p[n+1];
p[0]=0;
for(int i=1;i<=n;i++)
{
cin>>x[i];
p[i]=p[i-1]+x[i];
}
vector<int>ans;
for(int k=2;k<=n;k++)
{
bool ok=true;
for(int i=1;i<=n-k+1;i++)
{
int kol=(p[k+i-1]-p[i-1]);
if(kol%2==1)
{
ok=false;
break;
}
kol/=2;
set<int>prev;
prev.insert(0);
set<int>next;
for(int j=i;j<=i+k-1;j++)
{
for(auto ax:prev)
{
next.insert(ax+x[j]);
}
prev=next;
}
if(prev.count(kol)==0)
{
ok=false;
break;
}
}
if(ok)
{
ans.push_back(k);
}
}
cout<<ans.size()<<" ";
for(auto ax:ans)
{
cout<<ax<< " ";
}
cout<<endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |