Submission #1022396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022396		phoenix	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1072 ms	16228 KiB

bootfall

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
const int MOD3 = 999990011;
const int MOD4 = 1e9 + 9;
 
template<unsigned int MOD> 
struct mint {
    int v;
    mint() {}
    mint(long long val) : v(val - (val >= MOD) * MOD + (val < 0) * MOD) {}
    mint<MOD>& operator += (mint<MOD> other) {
        *this = mint(v + other.v);
        return *this;
    }
    mint<MOD>& operator -= (mint<MOD> other) {
        *this = mint(v - other.v);
        return *this;
    }
};
const int N = 550;
const int A = 250000;
 
mint<MOD1> dp1[A]{1};
mint<MOD2> dp2[A]{1};
mint<MOD3> dp3[A]{1};
mint<MOD4> dp4[A]{1};
int sum = 0;
 
void add(int val) {
    sum += val;
    for (int i = A - 1; i >= val; i--) {
        dp1[i] += dp1[i - val];
        dp2[i] += dp2[i - val];
        dp3[i] += dp3[i - val];
        dp4[i] += dp4[i - val];
    }   
}
 
bool check(int sum) {
    if (sum < 0 || sum >= A) return false;

    bool flag = true;
    flag &= (dp1[sum].v > 0);
    flag &= (dp2[sum].v > 0);
    flag &= (dp3[sum].v > 0);
    flag &= (dp4[sum].v > 0);
    return flag;
}
 
void del(int val) {
    sum -= val;
    for (int i = val; i < A; i++) {
        dp1[i] -= dp1[i - val];
        dp2[i] -= dp2[i - val];
        dp3[i] -= dp3[i - val];
        dp4[i] -= dp4[i - val];
    }
}
 
int n;
int a[N];

set<int> st;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) {
        add(a[i]);
    }
    if (sum & 1 || !check(sum / 2)) {
        cout << 0;
        return 0;
    }
    for (int i = 0; i < A; i++) st.insert(i);

    for (int i = 0; i < n; i++) {
        if (i) add(a[i - 1]);
        del(a[i]);
        if (st.empty()) {
            cout << 0;
            return 0;
        }
        int x = *st.begin();
        for (auto it = st.begin(); it != st.end(); it = st.upper_bound(x)) {
            x = *it;
            if ((x ^ sum) & 1) st.erase(it);  
            else {
                if (!check(sum - x >> 1) && !check(sum + x >> 1)) {
                    st.erase(it);
                }
            }
        }
    }
    cout << (int)st.size() << '\n';
    for (int c : st) cout << c << ' ';
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:96:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   96 |                 if (!check(sum - x >> 1) && !check(sum + x >> 1)) {
      |                            ~~~~^~~
bootfall.cpp:96:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |                 if (!check(sum - x >> 1) && !check(sum + x >> 1)) {
      |                                                    ~~~~^~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35