#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define FILEA "/home/prance/c/patyk/A.txt"

using namespace std;

vector<unsigned int> read_from_file() {
    vector<unsigned int> A;
    unsigned int number;
    ifstream file(FILEA);
    while (file >> number) A.push_back(number);
    file.close();
    return A;
}

bool find_k(unsigned long A_size) {
    const unsigned long dAsize = 2 * A_size;
    unsigned int i = 0;
    for (; i < dAsize; i++)
        if ((i + 1) * (i + 2) == dAsize)
            break;
    if (i == dAsize) {
        cout << "Nie znaleziono calkowitej liczby ciec, zadana instancja jest bledna" << endl;
        exit(1);
    }
    return true;
}

void erase(vector<unsigned int> &a, unsigned int r){
    auto it = find(a.begin(), a.end(), r);
    if (it != a.end()) a.erase(it);
}

vector<unsigned int> map(vector<unsigned int> A, unsigned int k) {
    vector<unsigned int> temp;
    vector<vector<unsigned int>> used;
    vector<unsigned int> result;

    if (is_sorted(A.begin(), A.end())) {
        auto it = A.end() - 1;
        auto it2 = A.end() - 2;
        result.push_back(*it - *it2);
        erase(A, *it - *it2);
        int max_sum = A.back();
        for (auto candidate = A.begin(); candidate != A.end(); ++candidate) {
            if (result.size() == k + 1 || A.empty()) {
                return result;
            }
            bool sum_found = true;
            int last;
            temp.clear();
            int sum = *candidate;
            for (auto res = result.end(); res != result.begin(); --res) {
                sum += *res;
                if (sum > max_sum) {
                    A.push_back(result.back());
                    last = result.back();
                    result.pop_back();
                    if (!used.empty())
                        for (auto &u : used.back()) {
                            A.push_back(u);
                        }
                    used.pop_back();
                    sort(A.begin(), A.end());
                    for (auto it = A.begin(); it != A.end(); ++it) {
                        if (*it > last) {
                            res = it;
                            break;
                        }
                    }
                    continue;
                }
                if (find(A.begin(), A.end(), sum) == A.end()) {
                    sum_found = false;
                    break;
                }
                temp.push_back(sum);
                erase(A, sum);
            }
            if (!sum_found) {
                for (auto &sums : temp)
                    A.push_back(sums);
                continue;
            } else {
                result.push_back(*candidate);
                erase(A, *candidate);
                used.push_back(temp);
                candidate = A.begin() + 1;
                continue;
            }
        }
    }

}

int main() {
    vector<unsigned int> A;
    A = read_from_file();
    cout << "dlugosc wektora: " << A.size() << endl;
    int k = find_k(A.size());
    cout << "k: " << k << endl << "zawartosc wektora: ";
    for (auto &a: A) cout << a << " ";
    cout << endl;
    vector<unsigned int> result = map(A, k);
    cout << "długość rozwiązania: " << result.size() << endl << "Rozwiązanie: ";
    for (auto &r: result) {
        cout << r << " ";
    }
    cout << endl;

    return 0;
}