Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "find_subsets.h"
- #include <stdexcept>
- #include <vector>
- #include <unordered_map>
- #include <cmath>
- #include <thread>
- #include <mutex>
- #include <atomic>
- #include <iostream>
- void FindSum(std::unordered_map<int64_t, size_t>& mp, size_t i, size_t j,
- const std::vector<int64_t>& data, const std::vector<size_t>& rev) {
- if (i == j) {
- return;
- }
- int n = j - i;
- size_t bound = pow(3, n);
- for (size_t k = 1; k < bound; ++k) {
- if (k > rev[k]) {
- continue;
- }
- int64_t sum = 0;
- size_t kk = k;
- int ind = i;
- while (kk != 0) {
- if (kk % 3 == 2) {
- sum += data[ind];
- } else if (kk % 3 == 1) {
- sum -= data[ind];
- }
- ind++;
- kk = kk / 3;
- }
- mp[sum] = k;
- }
- }
- void FindIndexes(size_t num, std::vector<size_t>& first, std::vector<size_t>& second, int i) {
- int ind = i;
- while (num != 0) {
- if (num % 3 == 2) {
- first.push_back(ind);
- } else if (num % 3 == 1) {
- second.push_back(ind);
- }
- ind++;
- num /= 3;
- }
- }
- Subsets subset;
- std::atomic<bool> fl;
- std::mutex mtx;
- template <class InputIt>
- void MyAdvance(InputIt& it, InputIt end, int n) {
- while (n-- > 0 && it != end) {
- std::advance(it, 1);
- }
- }
- bool Check(size_t first, size_t second) {
- int a = 0, b = 0, c = 0, d = 0;
- while (first != 0) {
- if (first % 3 == 2) {
- a++;
- } else if (first % 3 == 1) {
- b++;
- }
- first /= 3;
- }
- while (second != 0) {
- if (second % 3 == 2) {
- c++;
- } else if (second % 3 == 1) {
- d++;
- }
- second /= 3;
- }
- return (a + d != 0 && b + c != 0);
- }
- void Result(const std::unordered_map<int64_t, size_t>& mp1,
- const std::unordered_map<int64_t, size_t>& mp2, size_t sz, int i,
- const std::vector<size_t>& rev) {
- auto st = mp1.begin();
- MyAdvance(st, mp1.end(), i);
- for (; st != mp1.end() && !fl.load(); MyAdvance(st, mp1.end(), 8)) {
- int64_t key = st->first;
- bool fl1 = (mp2.find(key) != mp2.end());
- bool fl2 = (mp2.find(-1 * key) != mp2.end());
- if (fl1) {
- size_t vl = mp2.at(key);;
- if (Check(mp1.at(key), vl)) {
- std::vector<size_t> first, second;
- FindIndexes(mp1.at(key), first, second, 0);
- FindIndexes(vl, second, first, sz);
- fl.store(true);
- mtx.lock();
- subset = Subsets{first, second, true};
- mtx.unlock();
- return;
- }
- }
- if (fl2) {
- size_t vl = rev[mp2.at(-1 * key)];
- if (Check(mp1.at(key), vl)) {
- std::vector<size_t> first, second;
- FindIndexes(mp1.at(key), first, second, 0);
- FindIndexes(vl, second, first, sz);
- fl.store(true);
- mtx.lock();
- subset = Subsets{first, second, true};
- mtx.unlock();
- return;
- }
- }
- }
- }
- Subsets FindEqual(const std::unordered_map<int64_t, size_t>& mp1,
- const std::unordered_map<int64_t, size_t>& mp2, size_t sz,
- const std::vector<size_t>& rev) {
- fl.store(false);
- std::thread t1([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 0, rev); });
- std::thread t2([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 1, rev); });
- std::thread t3([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 2, rev); });
- std::thread t4([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 3, rev); });
- std::thread t5([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 4, rev); });
- std::thread t6([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 5, rev); });
- std::thread t7([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 6, rev); });
- std::thread t8([&mp1, &mp2, sz, &rev] { Result(mp1, mp2, sz, 7, rev); });
- t1.join();
- t2.join();
- t3.join();
- t4.join();
- t5.join();
- t6.join();
- t7.join();
- t8.join();
- if (fl) {
- return subset;
- }
- return Subsets{{}, {}, false};
- }
- Subsets FindEqualSumSubsets(const std::vector<int64_t>& data) {
- size_t sz = data.size() / 2;
- std::vector<size_t> rev(pow(3, data.size()));
- for (size_t i = 0; i < rev.size(); ++i) {
- size_t rev_i = 0;
- size_t ii = i;
- int64_t pw = 1;
- while (ii > 0) {
- rev_i += pw * (3 - ii % 3) % 3;
- pw *= 3;
- ii /= 3;
- }
- rev[i] = rev_i;
- }
- std::unordered_map<int64_t, size_t> mp1;
- std::unordered_map<int64_t, size_t> mp2;
- std::thread th1([&mp1, sz, &data, &rev] { FindSum(mp1, 0, sz, data, rev); });
- std::thread th2([&mp2, sz, &data, &rev] { FindSum(mp2, sz, data.size(), data, rev); });
- th1.join();
- th2.join();
- std::vector<size_t> first, second;
- if (mp1.find(0) != mp1.end()) {
- FindIndexes(mp1[0], first, second, 0);
- return Subsets{first, second, true};
- }
- if (mp2.find(0) != mp2.end()) {
- FindIndexes(mp2[0], first, second, sz);
- return Subsets{first, second, true};
- }
- return FindEqual(mp1, mp2, sz, rev);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement