oj.uz

Submission #1089171

# Submission time Handle Problem Language Result Execution time Memory
1089171 2024-09-16T06:48:42 Z vjudge1 Kpart (eJOI21_kpart) C++17
0 / 100
 2000 ms 612 KB 
#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]++;
        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,ll z=0){
    if(x==n){
       // if(z==1)cout<<bool(mp[s1-s2])<<'\n';
        //if(mp[s2-s1])cout<<s1<<' '<<s2<<'\n';
        return bool(mp[s1-s2]);
    }
    x++;
    ll ans=max(f2(x,n,s1+a[x],s2,z),f2(x,n,s1,s2+a[x],z));
    //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;

            f1(i-1,mid);
            ll z=0;
            if(k==4)z=1;

            ch=min(ch,f2(mid,i+k-1,0,0,z));

        }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';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 612 KB Time limit exceeded
2 Halted 0 ms 0 KB -