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

// equal_subset_sum.cpp
// Tìm hai subset khác nhau có cùng tổng cho n <= 42
// - Sử dụng meet-in-the-middle để kiểm tra các subset nằm hoàn toàn trong 1 nửa
// - Nếu chưa tìm được, dùng sampling (ngẫu nhiên / hoặc liệt kê khi n nhỏ) trên toàn bộ không gian tập con
// Đầu vào: n (<=42) rồi n số nguyên a[i]
// Đầu ra: in ra tổng S và hai tập con (danh sách chỉ số 0-based) có cùng tổng; nếu không tìm thấy in thông báo.

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

void print_solution(ll S, ull mask1, ull mask2, int n) {
    cout << "Found S = " << S << '\n';
    // in chỉ số 0-based
    vector<int> v1, v2;
    for (int i = 0; i < n; ++i) {
        if ((mask1 >> i) & 1ULL) v1.push_back(i);
        if ((mask2 >> i) & 1ULL) v2.push_back(i);
    }
    cout << "Subset 1 (indices, 0-based): ";
    for (size_t i = 0; i < v1.size(); ++i) {
        if (i) cout << ' ';
        cout << v1[i];
    }
    cout << '\n';
    cout << "Subset 2 (indices, 0-based): ";
    for (size_t i = 0; i < v2.size(); ++i) {
        if (i) cout << ' ';
        cout << v2[i];
    }
    cout << '\n';
    // optional: print values
    if (!v1.empty()) {
        cout << "Subset 1 values: ";
        for (size_t i = 0; i < v1.size(); ++i) {
            if (i) cout << ' ';
            // note: caller must have a in scope to print values; we'll skip here
            cout << "a[" << v1[i] << "]";
        }
        cout << '\n';
    }
}

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];

    if (n == 0) {
        cout << "No elements\n";
        return 0;
    }

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

    // 1) enumerate left subsets, detect duplicates inside left
    unordered_map<ll, ull> map_left; // sum -> mask (mask uses full n-bit representation: lower left bits used)
    map_left.reserve(L * 2);
    vector<ll> sums_left(L, 0);
    map_left[0] = 0ULL; // empty
    for (int mask = 1; mask < L; ++mask) {
        int lsb = mask & -mask;
        int prev = mask ^ lsb;
        int idx = __builtin_ctz((unsigned)lsb); // index inside left
        sums_left[mask] = sums_left[prev] + a[idx];
        ll s = sums_left[mask];
        ull fullmask = (ull)mask; // occupies bits [0..left-1]
        auto it = map_left.find(s);
        if (it != map_left.end()) {
            ull other = it->second;
            if (other != fullmask) {
                print_solution(s, other, fullmask, n);
                return 0;
            }
        } else {
            map_left[s] = fullmask;
        }
    }

    // 2) enumerate right subsets, detect duplicates inside right and cross with left
    unordered_map<ll, ull> map_right; // sum -> mask (full representation shifted)
    map_right.reserve(R * 2);
    vector<ll> sums_right(R, 0);
    map_right[0] = 0ULL; // empty (no bits set in right part)
    for (int mask = 1; mask < R; ++mask) {
        int lsb = mask & -mask;
        int prev = mask ^ lsb;
        int idx = __builtin_ctz((unsigned)lsb); // index inside right
        sums_right[mask] = sums_right[prev] + a[left + idx];
        ll s = sums_right[mask];
        ull fullmask = ((ull)mask) << left; // shift to high bits
        // duplicate inside right
        auto itR = map_right.find(s);
        if (itR != map_right.end()) {
            ull other = itR->second;
            if (other != fullmask) {
                print_solution(s, other, fullmask, n);
                return 0;
            }
        } else {
            map_right[s] = fullmask;
        }
        // cross left vs right: left subset sum == right subset sum
        auto itL = map_left.find(s);
        if (itL != map_left.end()) {
            ull leftmask = itL->second;
            // ensure different subsets overall
            if (leftmask != fullmask) {
                print_solution(s, leftmask, fullmask, n);
                return 0;
            }
        }
    }

    // 3) Nếu vẫn chưa có (ít khả năng theo giả thiết), thử sampling trên toàn bộ không gian subset
    //    Dùng bảng hash sum -> mask, sample nhiều mask (toàn bộ nếu n <= 22), hoặc random nếu n > 22.

    unordered_map<ll, ull> full_map;
    const ull MAX_SAMPLE = (1ULL << 21); // khoảng ~2 triệu
    ull limit_samples = 0;
    if (n <= 22) {
        limit_samples = 1ULL << n; // enumerate toàn bộ (2^n) nếu nhỏ
    } else {
        limit_samples = MAX_SAMPLE; // sample this many random subsets
    }
    full_map.reserve((size_t)min(limit_samples, (ull)2000000ULL) * 2);

    // if enumerating all subsets (n small)
    if (n <= 22) {
        ull total = 1ULL << n;
        vector<ll> dp(total, 0);
        for (ull mask = 1; mask < total; ++mask) {
            ull lsb = mask & -mask;
            ull prev = mask ^ lsb;
            int idx = __builtin_ctzll(lsb);
            dp[mask] = dp[prev] + a[idx];
            ll s = dp[mask];
            auto it = full_map.find(s);
            if (it != full_map.end()) {
                ull other = it->second;
                if (other != mask) {
                    print_solution(s, other, mask, n);
                    return 0;
                }
            } else {
                full_map[s] = mask;
            }
        }
    } else {
        // random sampling
        mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
        unordered_set<ull> seen_masks;
        seen_masks.reserve((size_t)min(limit_samples, (ull)2000000ULL));
        for (ull iter = 0; iter < limit_samples; ++iter) {
            ull mask = rng();
            if (n < 64) mask &= ((1ULL << n) - 1ULL);
            // avoid duplicate masks in sampling
            if (seen_masks.find(mask) != seen_masks.end()) continue;
            seen_masks.insert(mask);
            // compute sum
            ull tmp = mask;
            ll s = 0;
            while (tmp) {
                int b = __builtin_ctzll(tmp);
                s += a[b];
                tmp &= tmp - 1ULL;
            }
            auto it = full_map.find(s);
            if (it != full_map.end()) {
                ull other = it->second;
                if (other != mask) {
                    print_solution(s, other, mask, n);
                    return 0;
                }
            } else {
                full_map[s] = mask;
            }
        }
    }

    cout << "Không tìm được hai subset khác nhau cùng tổng (bất ngờ; có thể do giới hạn sampling)." << '\n';
    return 0;
}