제출 #173616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173616		aleks5d	Bootfall (IZhO17_bootfall)	C++17	44 / 100	148 ms	2040 KiB

bootfall

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>

using ll = long long int;
using ull = unsigned long long int;
using dd = double;
using ldd = long double;

namespace HASH {
const ll mod197 = 1e9 + 7;
const ll mod199 = 1e9 + 9;
const ll modfft = 998244353;
ll mod = mod199;
void Hplus(ll& h, ll b) {
    h += b;
    if (h > mod)
        h -= mod;
}

void Hminus(ll& h, ll b) {
    h -= b;
    if (h < 0)
        h += mod;
}

void Hmuliply(ll& h, ll b) {
    h *= b;
    h %= mod;
}

ll Hdivider(ll x) {
    if (x < 0)
        x += mod;
    ll ans = 1;
    ll n = mod - 2;
    while (n) {
        if (n & 1)
            Hmuliply(ans, x);
        n >>= 1;
        Hmuliply(x, x);
    }
    return ans;
}
}

namespace someUsefull {
template<typename T1, typename T2>
inline void checkMin(T1& a, T2 b) {
    if (a > b)
        a = b;
}

template<typename T1, typename T2>
inline void checkMax(T1& a, T2 b) {
    if (a < b)
        a = b;
}
}

//name spaces
using namespace std;
using namespace HASH;
using namespace someUsefull;
//end of name spaces

//defines
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()

#define NO cout << "NO" << '\n';
#define YES cout << "YES" << '\n';
//end of defines

//debug defines
#ifdef HOME
    #define debug(x) cout << #x << " " << x << endl;
    #define debug_p(x) cout << #x << " " << x.ff << " " << x.ss << endl;
    #define debug_v(x) {cout << #x << " "; for (auto ioi : x) cout << ioi << " "; cout << endl;}
    #define debug_vp(x) {cout << #x << " "; for (auto ioi : x) cout << '[' << ioi.ff << " " << ioi.ss << ']'; cout << endl;}
    #define debug_v_v(x) {cout << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cout << ioi2 << " "; cout << '\n';} cout << "*/" << #x << endl;}
    int jjj;
    #define wait() cin >> jjj;
    #define PO cout << "POMELO" << endl;
    #define OL cout << "OLIVA" << endl;
    #define gen_clock(x) ll x = clock(); cout << "Clock " << #x << " created" << endl;
    #define check_clock(x) cout << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();
    #define reset_clock(x) x = clock();
    #define say(x) cout << x << endl;
#else
    #define debug(x) 0;
    #define debug_p(x) 0;
    #define debug_v(x) 0;
    #define debug_vp(x) 0;
    #define debug_v_v(x) 0;
    #define wait() 0;
    #define PO 0;
    #define OL 0;
    #define gen_clock(x) 0;
    #define check_clock(x) 0;
    #define reset_clock(x) 0;
    #define say(x) 0;
#endif // HOME
//end of debug defines

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    vector<ll> dp(1e5);
    vector<int> canbe(1e5, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = dp.size() - 1; j >= arr[i]; --j) {
            Hplus(dp[j], dp[j - arr[i]]);
        }
    }
    int ma = 0;
    for (int j = dp.size() - 1; j > 0; --j)
    if (dp[j]) {
        ma = j;
        break;
    }
    if (ma & 1) {
        cout << 0;
        return;
    }
    if (dp[ma >> 1] == 0) {
        cout << 0;
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (i != -1) {
            for (int j = arr[i]; j < dp.size(); ++j) {
                Hminus(dp[j], dp[j - arr[i]]);
            }
        }
        int ma = 0;
        for (int i = dp.size() - 1; i > 0; --i) {
            if (dp[i]) {
                ma = i;
                break;
            }
        }
        debug(i);
        //vector<int> opa(dp.begin(), dp.begin() + ma + 1);
        //debug_v(opa);
        debug(ma);
        for (int i = 0; i * 2 <= ma; ++i) {
            if (dp[i]) {
                debug(i);
                debug(ma - i - i);
                ++canbe[ma - i - i];
            }
        }
        if (i != -1) {
            for (int j = dp.size() - 1; j >= arr[i]; --j) {
                Hplus(dp[j], dp[j - arr[i]]);
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i < dp.size(); ++i) {
        if (canbe[i] == n) {
            ans.push_back(i);
        }
    }
    cout << ans.size() << '\n';
    for (int i : ans)
        cout << i << " ";

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    t = 1;
  // cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
        cout << '\n';
    }
    return 0;

}

/*
5
3 2
3 -2
-2 -2
-2 2
0 0
*/

컴파일 시 표준 에러 (stderr) 메시지

bootfall.cpp: In function 'void solve()':
bootfall.cpp:137:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = arr[i]; j < dp.size(); ++j) {
                                  ~~^~~~~~~~~~~
bootfall.cpp:92:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
bootfall.cpp:148:9: note: in expansion of macro 'debug'
         debug(i);
         ^~~~~
bootfall.cpp:92:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
bootfall.cpp:151:9: note: in expansion of macro 'debug'
         debug(ma);
         ^~~~~
bootfall.cpp:92:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
bootfall.cpp:154:17: note: in expansion of macro 'debug'
                 debug(i);
                 ^~~~~
bootfall.cpp:92:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
bootfall.cpp:155:17: note: in expansion of macro 'debug'
                 debug(ma - i - i);
                 ^~~~~
bootfall.cpp:166:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dp.size(); ++i) {
                     ~~^~~~~~~~~~~

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