Submission #60763883

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto&& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;

ll solve(vector<ll> tmp) {
    ll ans = 0;
    vector<pair<vector<ll>, vector<ll>>> v;
    {
        vector<ll> v1, v2;
        int n = tmp.size();
        rep(i, n) {
            if(tmp[i] & 1) v1.pb(tmp[i]);
            else v2.pb(tmp[i]);
        }
        ll sz = v1.size();
        ans += sz * (sz - 1) / 2;
        ans += accumulate(all(v1), 0LL) * (sz - 1);
        sz = v2.size();
        ans += sz * (sz - 1) / 2;
        ans += accumulate(all(v2), 0LL) * (sz - 1);

        v.push_back({v1, v2});
    }
    while(!v.empty()) {
        auto [v1, v2] = v.back();
        v.pop_back();
        if(v1.empty() or v2.empty()) continue;
        for(ll &x : v1) x /= 2;
        for(ll &x : v2) x /= 2;
        vector<ll> nx1, nx2, nx3, nx4;
        foa(x, v1) {
            if(x & 1) nx1.pb(x);
            else nx2.pb(x);
        }
        foa(x, v2) {
            if(x & 1) nx3.pb(x);
            else nx4.pb(x);
        }
        {
            ll sz1 = nx1.size();
            ll sz2 = nx3.size();
            ans += sz1 * sz2;
            ans += sz1 * accumulate(all(nx3), 0LL);
            ans += sz2 * accumulate(all(nx1), 0LL);
        }
        {
            ll sz1 = nx2.size();
            ll sz2 = nx4.size();
            ans += sz1 * sz2;
            ans += sz1 * accumulate(all(nx4), 0LL);
            ans += sz2 * accumulate(all(nx2), 0LL);
        }
        v.push_back({nx1, nx4});
        v.push_back({nx2, nx3});
    }
    return ans;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n);
    ll ans = 0;
    rep(i, n) {
        cin >> a[i];
        {
            ll x = a[i] * 2;
            while(x % 2 == 0) x /= 2;
            ans += x;
        }
    }
    while(!a.empty()) {
        if(accumulate(all(a), 0LL) == 0LL) break;
        n = a.size();
        vector<ll> v0, v1;
        rep(i, n) {
            if(a[i] & 1) v1.pb(a[i]);
            else v0.pb(a[i]);
        }
        ans += accumulate(all(v1), 0LL) * (ll)v0.size();
        ans += accumulate(all(v0), 0LL) * (ll)v1.size();
        int sz = v0.size();
        rep(i, sz) v0[i] >>= 1;
        sz = n - sz;
        rep(i, sz) v1[i] >>= 1;
        ans += solve(v1);
        swap(a, v0);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result