Two rectangles

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>

typedef std::tuple<unsigned long long, unsigned long long> rectangle;
typedef std::tuple<rectangle, rectangle> answer;

rectangle best_permiter(const unsigned long long p) {
    unsigned long long best = 2*(p + 1);
    rectangle answer(1, p);
    for(unsigned long long i = 2; i*i <= p; ++i) {
        if(p % i == 0 && 2*(p/i+i) < best) {
            answer = rectangle(p/i, i);
            best = 2 * (p/i + i);
        }
    }
    return answer;
}

inline unsigned long long permiter(const rectangle& x) {
    return 2 * (std::get<0>(x) + std::get<1>(x));
}

std::vector<rectangle> make_cache() {
    constexpr size_t cache_size = 1300U*1000U;
    std::vector<rectangle> cache(cache_size + 1);
    cache.emplace_back(0,0);
    for(size_t i = 1; i < cache.size(); ++i) {
        cache[i] = rectangle(1, i);
    }
    for(unsigned i = 2; i < cache_size; ++i) {
        for(size_t j = i; j < cache.size(); j += i) {
            if(permiter(cache[j]) > 2 * (i + j/i)) {
                cache[j] = rectangle(i, j/i);
            }
        }
    }
    return cache;
}

answer solve(const unsigned long long begin, const unsigned long long end,
             const unsigned long long p) {
    if(p == 2) {
        return answer(rectangle(1,1), rectangle(1,1));
    }
    if(p < 100000) {
           answer result;
           unsigned long long square = sqrt(p), best = p*8;
           for(unsigned long long i = 1; i <= square; ++i) {
             for(unsigned long long j = 1; j * i < p; ++j) {
               auto temp = best_permiter(p - i*j);
               if(permiter(temp) + 2*(i+j) < best) {
                 result = answer(temp, rectangle(i, j));
                 best = permiter(temp) + 2 * (i + j);
                }
              }
            }
           return result;
          }
    const static std::vector<rectangle> cache = make_cache();
    answer result;
    unsigned long long best = 0;
    bool first = true;
    unsigned long long square = sqrt(p);
    if(p < 100) {
        square = p-1;
    }
    for(unsigned long long i = begin; i <= end && i < square; ++i) {
        const auto first_side = square - i;
        const auto second_side = p / first_side;
        if(second_side == 0 || first_side * second_side == p) {
            continue;
        }
        auto first_rectangle = rectangle(first_side, second_side);
        auto rest = p - first_side * second_side;
        if(rest > cache.size()) {
            continue;
        }
        auto second_rectangle = rest < cache.size() ? cache[rest] :
                                        best_permiter(rest);
        auto sum_of_sides = std::get<0>(second_rectangle) +
                            std::get<1>(second_rectangle) +
                            std::get<0>(first_rectangle)  +
                            std::get<1>(first_rectangle);
        if(first == true || sum_of_sides < best) {
            result = answer(first_rectangle, second_rectangle);
            best = sum_of_sides;
            first = false;
        }
    }
    return result;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    unsigned t;
    std::cin >> t;
    for(unsigned counter = 0; counter < t; ++counter) {
        unsigned long long p;
        std::cin >> p;
        unsigned long long begin = 0, end = 1000000;
        auto result = solve(begin, end, p);
        auto sum_of_permiter = permiter(std::get<0>(result)) +
                              permiter(std::get<1>(result));
        std::cout << sum_of_permiter << '\n';
        std::cout << std::get<0>(std::get<0>(result)) << ' '
                  << std::get<1>(std::get<0>(result)) << '\n'
                  << std::get<0>(std::get<1>(result)) << ' '
                  << std::get<1>(std::get<1>(result)) << '\n';
    }
}