oj.uz

Submission #1089333

# Submission time Handle Problem Language Result Execution time Memory
1089333 2024-09-16T10:09:57 Z vjudge1 Kpart (eJOI21_kpart) C++17
10 / 100
 2000 ms 2052 KB 
/**
 *    data : 09.07.2024  
 *     
**/
#include <bits/stdc++.h>
// #include "algo/turnikmen.h"

using namespace std;


#define int long long
#define bitt __builtin_popcountll
#define bitzero __builtin_clz

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

void fReopen () {
        #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        #endif
}


signed main (/*  time : 9:17 AM   */) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

      //  fReopen();

        int t; cin >> t;
        while (t --> 0) {
                int n; cin >> n;

                vector<int> a(n); for (auto &x : a) cin >> x;
                vector<int> pref(n + 1);
                vector<int> ans;
                for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i]; 
                for (int len = 2; len <= n; len++) {
                        int ok = 1;
                        const int N = 1e5 + 3;
                        vector<int> st(N, -1);
                        set<int> d;
                        int mx = -2e9;
                        for (int i = 0; i + len <= n; i++) {
                                int sum = pref[i + len] - pref[i];
                                mx = max(mx, sum);
                                if (sum % 2 == 1) {
                                        ok = 0;
                                        break;
                                }
                                if (st[sum] == -1)
                                        st[sum] = i;
                                d.insert(sum);

                        }
                        if (!ok) continue;
                        // cout << len << "  ";
                        for (auto s : d) {
                                // cout << s << ' ';
                                bitset<131072> dp;
                                // dp.reset();
                                dp[0] = 1;
                                for (int i = st[s];  i < st[s] + len; i++) {
                                        if (a[i] > s / 2) continue;
                                        // dp[i] = 1;
                                        dp |= (dp << a[i]);
                                }
                                // cout << dp << '\n';
                                ok &= (dp[s / 2] == 1);

                        }
                        // cout << endl;
                        if (ok) ans.push_back(len);
                }
                cout << ans.size() << endl;
                for (auto to : ans) cout << to << ' ';
                cout << endl;
        }


}

Compilation message

Main.cpp: In function 'void fReopen()':
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2052 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 1840 KB Output is correct
2 Execution timed out 2045 ms 1840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

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