#include "find_subsets.h"
#include <stdexcept>
#include <vector>
#include <unordered_map>
#include <thread>
#include <iostream>
#include <atomic>

int64_t tpow[16] = {1,    3,     9,     27,     81,     243,     729,     2187,
                    6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907};

void Fill(const std::vector<int64_t>& data, std::unordered_map<int64_t, int64_t>* mp) {
    int64_t mask, sum, mod;
    for (int64_t i = 1; i < tpow[data.size()]; i++) {
        mask = i;
        sum = 0;
        for (int j = 0; mask; j++) {
            mod = mask % 3;
            if (mod == 1) {
                sum += data[j];
            } else if (mod == 2) {
                sum -= data[j];
            }
            mask /= 3;
        }
        (*mp)[sum] = i;
    }
}

Subsets GetSubsets(int64_t mask) {
    Subsets res;
    int j = 0;
    while (mask) {
        int mod = mask % 3;
        if (mod == 1) {
            res.first_indices.push_back(j);
        } else if (mod == 2) {
            res.second_indices.push_back(j);
        }
        mask /= 3;
        j++;
    }
    return res;
}

Subsets FindEqualSumSubsets(const std::vector<int64_t>& data) {
    int sz = data.size();
    std::vector<int64_t> data1;
    std::vector<int64_t> data2;
    for (int i = 0; i < sz / 2; i++) {
        data1.push_back(data[i]);
    }
    for (int i = sz / 2; i < sz; i++) {
        data2.push_back(data[i]);
    }
    std::unordered_map<int64_t, int64_t> first_half;
    std::unordered_map<int64_t, int64_t> second_half;

    std::thread th1(Fill, data1, &first_half);
    std::thread th2(Fill, data2, &second_half);
    th1.join();
    th2.join();

    for (auto& [key, val] : first_half) {
        if (second_half.count(-key)) {
            Subsets buf = GetSubsets(second_half[-key] * tpow[sz / 2] + val);
            if (!buf.first_indices.empty() && !buf.second_indices.empty()) {
                buf.exists = 1;
                return buf;
            }
        }
    }

    if (first_half.count(0)) {
        auto res = GetSubsets(first_half[0]);
        if (!res.first_indices.empty() && !res.second_indices.empty()) {
            res.exists = true;
            return res;
        }
    }

    if (second_half.count(0)) {
        Subsets res = GetSubsets(second_half[0] * tpow[sz / 2]);
        if (!res.first_indices.empty() && !res.second_indices.empty()) {
            res.exists = true;
            return res;
        }
    }

    Subsets res;
    res.exists = 0;
    return res;
}