oj.uz

Submission #549140

# Submission time Handle Problem Language Result Execution time Memory
549140 2022-04-15T09:47:52 Z spike1236 Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 480 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define veci vector <int>
#define ll long long
#define sz(_v) (int)_v.size()

const int MAXN = 1e5 + 10;
///const int MOD = 1e9 + 7;
unsigned int dp[MAXN];
int S, n;
int a[1010];
int pref[1010];

void del(int x) {
    for(int i = x; i <= S; ++i) dp[i] -= dp[i - x];
    ///if(dp[i] < 0) dp[i] += MOD;
}

void add(int x) {
    for(int i = S; i >= x; --i) dp[i] += dp[i - x];
    ///if(dp[i] >= MOD) dp[i] -= MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    dp[0] = 1;
    for(int cs = 1; cs <= t; ++cs) {
        cin >> n;
        int gc = 0;
        for(int i = 1; i <= n; ++i) {
            cin >> a[i];
            gc = __gcd(gc, a[i]);
        }
        for(int i = 1; i <= n; ++i) {
            a[i] /= gc;
            pref[i] = pref[i - 1] + a[i];
        }
        veci ans;
        for(int len = 2; len <= n; ++len) {
            char can = 1;
            for(int i = 1; i + len - 1 <= n; ++i) {
                if((pref[i + len - 1] - pref[i - 1]) % 2 != 0) {
                    can = 0;
                    break;
                }
            }
            if(!can) continue;
            multiset <int> st;
            for(int i = 1; i <= len; ++i) st.insert(a[i]);
            if(*st.rbegin() > pref[len] / 2) continue;
            for(int i = len + 1; i <= n; ++i) {
                st.erase(st.find(a[i - len]));
                st.insert(a[i]);
                if(*st.rbegin() > (pref[i] - pref[i - len]) / 2 || *st.begin() > (pref[i] - pref[i - len]) / 4) {
                    can = 0;
                    break;
                }
            }
            if(!can) continue;
            S = pref[len];
            for(int l = 1; l <= len; ++l) add(a[l]);
            if(dp[S >> 1] == 0) {
                for(int i = 1; i <= S; ++i) dp[i] = 0;
                continue;
            }
            for(int r = len + 1; r <= n; ++r) {
                del(a[r - len]);
                S -= a[r - len];
                S += a[r];
                add(a[r]);
                if(dp[S >> 1] == 0) {
                    for(int i = 1; i <= S; ++i) dp[i] = 0;
                    can = 0;
                    break;
                }
            }
            if(can) {
                for(int i = 1; i <= S; ++i) dp[i] = 0;
                ans.pb(len);
            }
        }
        cout << sz(ans) << ' ';
        for(auto it : ans) cout << it << ' ';
        cout << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 360 KB Output is correct
2 Correct 408 ms 376 KB Output is correct

Subtask #3
0 / 70.0

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