Submission #1089185

#TimeUsernameProblemLanguageResultExecution timeMemory
1089185vjudge1Kpart (eJOI21_kpart)C++17
0 / 100
2070 ms844 KiB
#include <bits/stdc++.h> //qwerty47924692 using namespace std; using ll = int; const ll N=2e5+29; ll n,t,a[N]; map<ll,ll>mp; void f1(ll x,ll n,ll s1=0,ll s2=0){ if(x==n){ mp[s1-s2]=1; return; } x++; f1(x,n,s1+a[x],s2); f1(x,n,s1,s2+a[x]); } ll f2(ll x,ll n,ll s1=0,ll s2=0){ if(x==n){ // if(z==1)cout<<bool(mp[s1-s2])<<'\n'; // if(mp[s1-s2])cout<<s1<<' '<<s2<<'\n'; return (mp[s1-s2]); } x++; // cout<<x<<' '; ll ans=max(f2(x,n,s1+a[x],s2),f2(x,n,s1,s2+a[x])); //if(z==1)cout<<ans; return ans; } void solve(){ cin>>n; for(ll i=1;i<=n;i++){ cin>>a[i]; } vector<ll>v; for(ll k=1;k<=n;k++){ mp.clear(); ll ch=1; for(ll i=1;i+k-1<=n;i++){ ll mid=((i+k-1)+i)>>1; if(k==1&&a[i])ch=0; f1(i-1,mid); ch=min(ch,f2(mid,i+k-1)); // if(k==1)cout<<f2(mid,i+k-1); }if(ch)v.push_back(k); ch=1; } cout<<v.size(); for(ll i:v){ cout<<' '<<i; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll t; cin>>t; while(t--){ solve(); cout<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...