oj.uz

Submission #582441

# Submission time Handle Problem Language Result Execution time Memory
582441 2022-06-23T19:05:55 Z TimDee Kpart (eJOI21_kpart) C++14
10 / 100
 2000 ms 2136 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    #define paiu return
    #define moment 0;
     
    #define int long long
    #define ll long long
     
    #define forr(i,x) for (int i=0; i<x; i++)
    #define forn(i,x) for (int i=0; i<x; i++)
    #define forrr(i,j,x) for (int i=j; i<x; i++)
     
    #define di(a,n) deque<int> a(n,0)
    #define dll(a,n) deque<ll> a(n,0)
    #define vi(a,n) vector<int> a(n,0)
    #define vll(a,n) vector<ll> a(n,0)
     
    //cringe define
    #define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
    vector<int> ___makeprefsum(vector<int>&a) {
        int n=a.size();
        vi(pr,n+1);
        forn(i,n) pr[i+1]=pr[i]+a[i];
        return pr;
    }
    #define prefsum(pr,a) vector<int> pr=___makeprefsum(a);
     
    #define all(v) v.begin(),v.end()
    #define rall(v) v.rbegin(),v.rend()
     
    #define pb(x) push_back(x)
    #define pf pop_front();
    #define last(c) c[c.size()-1]
     
    #define f first
    #define s second
     
    #define pi pair<int, int>
    #define mp(x,y) make_pair(x, y)
     
    const ll mod = 1000000007;
    const double ppi = acos(0) * 2;
         
    const int maxn = 1e5+1;
    const int inf = INT_MAX;
    const ll linf = LLONG_MAX;
    const ll mmod = 998244353;
     
    vector<bitset<maxn>> ks(deque<int> a, int s) {
     
        int n = a.size();
     
        vector<bitset<maxn>> dp(n+1);
        //forn(i,n+1) dp[i].assign(s+3,0);
     
        dp[0][0]=1;
     
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=s; j++) {
                dp[i][j]=dp[i-1][j];
                if (j-a[i-1]>=0 && dp[i-1][j-a[i-1]]) dp[i][j]=dp[i-1][j-a[i-1]];
            }
        }
     
        //forn(i,n+1) {
        //    forn(j,25) cout<<dp[i][j]<<' '; cout<<'\n';
        //}
        //cout<<'\n';
     
        return dp;
     
    }
     
    void solve() {
        
        int n; cin>>n;
        vii(a,n);
     
        vector<int> ans;
     
        for (int k=1; k<=n; k++) {
     
            deque<int> b;
            int s=0;
            forn(i,k) { b.pb(a[i]); s+=a[i]; }
            vector<bitset<maxn>> dp;
            int foo=1;
     
            dp = ks(b,s);
     
            //forn(j,b.size()) cout<<b[j]<<' ';
            //cout<<' '<<s<<'\n';
     
            if (dp[k][s/2]==0 || (s%2)) {
                continue;
            }
     
            for (int i=k; i<n; i++) {
                
                b.pb(a[i]);
                s+=a[i];
                b.pop_front();
                s-=a[i-k];
     
                //forn(j,b.size()) cout<<b[j]<<' ';
                //cout<<' '<<s<<'\n';
     
                dp = ks(b,s);
                if (dp[k][s/2]==0 || (s%2)) {
                    foo=0;
                    break;
                } 
     
            }
     
            if (foo) ans.pb(k);
     
        }
     
        n=ans.size(); cout<<n<<' ';
        forn(i,n) cout<<ans[i]<<' '; cout<<'\n';
     
    }
     
    int32_t main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     
        //init_primes();
        
        int t=1;
        cin>>t;
        
        while(t--) solve();
        
        paiu moment
    }

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:11:23: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   11 |     #define forn(i,x) for (int i=0; i<x; i++)
      |                       ^~~
Main.cpp:122:9: note: in expansion of macro 'forn'
  122 |         forn(i,n) cout<<ans[i]<<' '; cout<<'\n';
      |         ^~~~
Main.cpp:122:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  122 |         forn(i,n) cout<<ans[i]<<' '; cout<<'\n';
      |                                      ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 1416 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 2136 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 2050 ms 2068 KB Time limit exceeded
2 Halted 0 ms 0 KB -