0lwu6n - Online C++0x Compiler & Debugging Tool

// find_S.cpp
// In ra một giá trị S sao cho tồn tại hai subset khác nhau (rời nhau sau khi lấy hiệu)
// có cùng tổng = S. Nếu không tìm thấy in IMPOSSIBLE.
// n <= 40, a[i] > 0

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int left = n / 2;
    int right = n - left;
    int L = 1 << left;
    int R = 1 << right;

    unordered_map<ll, ull> map_left; // sum -> mask (bits in low positions for left)
    map_left.reserve(max(16, L*2));

    // enumerate left; detect duplicate sums inside left
    vector<ll> sum_left(L, 0);
    for (int mask = 0; mask < L; ++mask) {
        if (mask == 0) {
            sum_left[mask] = 0;
        } else {
            int lsb = mask & -mask;
            int prev = mask ^ lsb;
            int idx = __builtin_ctz((unsigned)lsb);
            sum_left[mask] = sum_left[prev] + a[idx];
        }
        ll s = sum_left[mask];
        auto it = map_left.find(s);
        if (it != map_left.end()) {
            ull other = it->second;
            if (other != (ull)mask) {
                cout << s << '\n';
                return 0;
            }
        } else {
            map_left[s] = (ull)mask;
        }
    }

    // enumerate right; detect duplicate inside right and cross with left
    unordered_map<ll, ull> map_right;
    map_right.reserve(max(16, R*2));
    vector<ll> sum_right(R, 0);
    for (int mask = 0; mask < R; ++mask) {
        if (mask == 0) {
            sum_right[mask] = 0;
        } else {
            int lsb = mask & -mask;
            int prev = mask ^ lsb;
            int idx = __builtin_ctz((unsigned)lsb); // index inside right
            sum_right[mask] = sum_right[prev] + a[left + idx];
        }
        ll s = sum_right[mask];
        ull fullmask = ((ull)mask) << left; // mask in full n-bit space
        // duplicate in right
        auto itR = map_right.find(s);
        if (itR != map_right.end()) {
            ull other = itR->second;
            if (other != fullmask) {
                cout << s << '\n';
                return 0;
            }
        } else {
            map_right[s] = fullmask;
        }
        // cross left vs right
        auto itL = map_left.find(s);
        if (itL != map_left.end()) {
            ull leftmask = itL->second;
            // leftmask and fullmask are in disjoint bit ranges -> valid
            cout << s << '\n';
            return 0;
        }
    }

    // As a fallback (practically shouldn't happen under given constraints), try
    // enumerating all subsets if n small
    if (n <= 22) {
        unordered_map<ll, ull> full;
        ull tot = 1ULL << n;
        for (ull mask = 0; mask < tot; ++mask) {
            ll s = 0;
            ull tmp = mask;
            while (tmp) {
                int b = __builtin_ctzll(tmp);
                s += a[b];
                tmp &= tmp - 1ULL;
            }
            auto it = full.find(s);
            if (it != full.end()) {
                ull other = it->second;
                if (other != mask) {
                    cout << s << '\n';
                    return 0;
                }
            } else full[s] = mask;
        }
    }

    cout << "IMPOSSIBLE\n";
    return 0;
}