mrm0Gz - Online C++ Compiler & Debugging Tool

#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 l = n/2;
    int r = n - l;

    unordered_map<ll, ull> left_map;
    left_map.reserve(1u << max(0, min(20, l))); // reserve heuristics

    // tất cả subset của nửa trái, lưu sum -> fullmask (mask trên toàn mảng, thấp)
    for(ull mask = 0; mask < (1ull << l); ++mask){
        ll s = 0;
        for(int i = 0; i < l; ++i){
            if(mask & (1ull << i)) s += a[i];
        }
        ull fullmask = mask; // thấp l bit
        auto it = left_map.find(s);
        if(it != left_map.end()){
            if(it->second != fullmask){ // đảm bảo khác nhau
                // in kết quả:
                ull m1 = it->second, m2 = fullmask;
                cout << s << '\n';
                // subset 1
                vector<int> idx1, idx2;
                for(int i = 0; i < n; ++i){
                    if(m1 & (1ull << i)) idx1.push_back(i);
                }
                for(int i = 0; i < n; ++i){
                    if(m2 & (1ull << i)) idx2.push_back(i);
                }
                // in chỉ số 1-based và giá trị
                cout << idx1.size();
                for(int x : idx1) cout << ' ' << (x+1);
                cout << '\n';
                for(int x : idx1) cout << a[x] << ( (&x == &idx1.back()) ? '\n' : ' ');
                cout << idx2.size();
                for(int x : idx2) cout << ' ' << (x+1);
                cout << '\n';
                for(int x : idx2) cout << a[x] << ( (&x == &idx2.back()) ? '\n' : ' ');
                return 0;
            }
        } else {
            left_map[s] = fullmask;
        }
    }

    unordered_map<ll, ull> right_map;
    right_map.reserve(1u << max(0, min(20, r)));

    // tất cả subset của nửa phải, lưu sum -> fullmask (đã dịch lên bit cao)
    for(ull mask = 0; mask < (1ull << r); ++mask){
        ll s = 0;
        for(int i = 0; i < r; ++i){
            if(mask & (1ull << i)) s += a[l + i];
        }
        ull fullmask = (mask << l); // dịch sang các bit cao
        auto it = right_map.find(s);
        if(it != right_map.end()){
            if(it->second != fullmask){
                ull m1 = it->second, m2 = fullmask;
                cout << s << '\n';
                vector<int> idx1, idx2;
                for(int i = 0; i < n; ++i){
                    if(m1 & (1ull << i)) idx1.push_back(i);
                }
                for(int i = 0; i < n; ++i){
                    if(m2 & (1ull << i)) idx2.push_back(i);
                }
                cout << idx1.size();
                for(int x : idx1) cout << ' ' << (x+1);
                cout << '\n';
                for(int x : idx1) cout << a[x] << ( (&x == &idx1.back()) ? '\n' : ' ');
                cout << idx2.size();
                for(int x : idx2) cout << ' ' << (x+1);
                cout << '\n';
                for(int x : idx2) cout << a[x] << ( (&x == &idx2.back()) ? '\n' : ' ');
                return 0;
            }
        } else {
            right_map[s] = fullmask;
        }
    }

    // giao giữa left và right: nếu sum xuất hiện ở cả hai, lấy hai mask (kiểm tra khác nhau)
    for(auto &p : left_map){
        ll s = p.first;
        ull m1 = p.second;
        auto it = right_map.find(s);
        if(it != right_map.end()){
            ull m2 = it->second;
            if(m1 == m2) continue; // (chỉ có thể xảy ra khi cả hai bằng 0) bỏ qua
            cout << s << '\n';
            vector<int> idx1, idx2;
            for(int i = 0; i < n; ++i){
                if(m1 & (1ull << i)) idx1.push_back(i);
            }
            for(int i = 0; i < n; ++i){
                if(m2 & (1ull << i)) idx2.push_back(i);
            }
            cout << idx1.size();
            for(int x : idx1) cout << ' ' << (x+1);
            cout << '\n';
            for(int x : idx1) cout << a[x] << ( (&x == &idx1.back()) ? '\n' : ' ');
            cout << idx2.size();
            for(int x : idx2) cout << ' ' << (x+1);
            cout << '\n';
            for(int x : idx2) cout << a[x] << ( (&x == &idx2.back()) ? '\n' : ' ');
            return 0;
        }
    }

    // theo giả thiết đề, không nên tới đây
    cout << "Khong tim thay\n";
    return 0;
}