bear_sums.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <optional>
#include <tuple>
#include <vector>

#include <thread>
#include <map>
#include <iterator>
#include <fstream>
#include <random>
#include <string>

using s64 = std::int64_t;
struct Element {
    s64 num;
    std::size_t idx;
    inline bool operator<(const Element& rhs) {
        if (num == rhs.num)
            return idx < rhs.idx;
        return num < rhs.num;
    }
    friend std::ostream& operator<<(std::ostream& stream, const Element& element) {
        return stream << element.num << ' ' << element.idx;
	}
};
using Iter = std::vector<Element>::const_iterator;

std::optional<std::pair<s64, s64>> FindComplements(const std::vector<Element>& set, const s64 sum) {
    static constexpr auto TransformPairs = [](const Iter& a, const Iter& b) {
        return std::make_pair(std::max(a->idx, b->idx), std::min(a->idx, b->idx));
    };
    std::pair<Iter, Iter> out = {set.end(), set.end()};
    for (auto it = set.begin(), end_it = set.end() - 1; it != set.end(); ++it) {
        while (end_it->num > sum - it->num)
            if (end_it == it)
                break;
            else
                --end_it;

        if (end_it->num == it->num)
            end_it = it + 1;

        if (it->num + end_it->num == sum &&
            (out.first == set.end() ||
             TransformPairs(it, end_it) < TransformPairs(out.first, out.second)))
            out = {end_it, it};
    }
    if (out.first == set.end())
        return {};

    auto output = std::make_pair(out.first->num, out.second->num);
    return std::min(output, std::make_pair(output.second, output.first));
}

using IterB = std::map<s64, std::size_t>::const_iterator;
std::optional<std::pair<s64, s64>> FindComplementB(const std::map<s64, std::size_t>& set,
                                                   const s64 sum,
                                                   const std::vector<std::size_t> half_pos) {
    static constexpr auto TransformPairs = [](const auto& a, const auto& b) {
        return std::make_pair(std::max(a->second, b->second), std::min(a->second, b->second));
    };
    std::pair<IterB, IterB> out = {set.end(), set.end()};
    for (auto it = set.begin(), end_it = --set.end(); it != set.end(); it++) {
        while (end_it->first > sum - it->first)
            if (end_it == set.begin())
                break;
            else
                end_it--;

        if (end_it == it) {
            if (half_pos.size() >= 2 &&
                (out.first == set.end() ||
                 std::make_pair(half_pos[1], half_pos[0]) < TransformPairs(out.first, out.second)))
                return {{it->first, it->first}};
            break;
        }

        if (it->first + end_it->first == sum &&
            (out.first == set.end() ||
             TransformPairs(it, end_it) < TransformPairs(out.first, out.second)))
            out = {end_it, it};
    }
    if (out.first == set.end())
        return {};

    auto output = std::make_pair(out.first->first, out.second->first);
    return std::min(output, std::make_pair(output.second, output.first));
}

int main() {
    unsigned T = 0;
    std::cin >> T;
    // std::vector<Element> nums;
    std::vector<std::thread> threads;
    for (unsigned i = 0; i < std::thread::hardware_concurrency(); ++i)
        threads.push_back(std::thread([] {
            std::random_device rand;
            std::vector<Element> nums;
            for (std::uint64_t i = 0; i < UINT64_MAX; ++i) {
                s64 S = rand();
                unsigned E = 20000;
                // std::cin >> S >> E;
                if (E == 0) {
                    std::cout << "!OK\n";
                    continue;
                }
                nums.resize(E);
                for (std::size_t j = 0; j < E; j++) {
                    s64 num;
                    // std::cin >> element;
                    num = rand();
                    nums[j] = {num, j};
                }
                std::sort(nums.begin(), nums.end());
                std::map<s64, std::size_t> map;
                std::vector<std::size_t> middle_pos;
                for (auto element : nums) {
                    map.emplace(element.num, element.idx);
                    if (S % 2 == 0 && element.num == S / 2)
                        middle_pos.push_back(element.idx);
                }
                auto result = FindComplements(nums, S);
                auto result_b = FindComplementB(map, S, middle_pos);
                if (result != result_b) {
                    std::ofstream log(std::to_string(i));
                    if (result)
                        log << result->first << ' ' << result->second << '\n';
                    else
                        log << "!OK\n";
                    if (result_b)
                        log << result_b->first << ' ' << result_b->second << '\n';
                    else
                        log << "!OK\n";
                    
					for (auto num : nums)
                        log << num << '\n';
                }
                nums.clear();
            }
        }));
    for (auto& thread : threads)
        thread.join();
    return 0;
}