bear_sums.cpp

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

using s64 = std::int64_t;
using Element = std::pair<s64, std::size_t>;
using Iter = std::map<s64, std::size_t>::const_iterator;

std::optional<std::pair<s64, s64>> FindComplements(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<Iter, Iter> 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::map<s64, std::size_t> nums;
    for (unsigned i = 0; i < T; i++) {
        s64 S = 0;
        unsigned E = 0;
        std::cin >> S >> E;
        if (E == 0) {
            std::cout << "!OK\n";
            continue;
		}
        std::optional<s64> half;
        if (!(S % 2))
            half.emplace(S / 2);
        std::vector<std::size_t> half_pos;
        for (std::size_t j = 0; j < E; j++) {
            s64 element;
            std::cin >> element;
            if (element == half)
                half_pos.push_back(j);
            nums.emplace(element, j);
        }
        auto result = FindComplements(nums, S, half_pos);
        if (result)
            std::cout << result->first << ' ' << result->second << '\n';
        else
            std::cout << "!OK\n";
        nums.clear();
    }
    return 0;
}