Submission #1262680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262680		podvorniy	Table Tennis (info1cup20_tabletennis)	C++20	35 / 100	40 ms	10564 KiB

tabletennis

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <map>


std::vector<int> check(long long S, const std::vector<int>& A, int N) {
    if (N == 0) {
        return {};
    }
    
    std::vector<int> solution;
    solution.reserve(N);

    int l = 0;
    int r = A.size() - 1;

    while (l < r) {
        long long current_sum = (long long)A[l] + A[r];
        if (current_sum == S) {
            // Эта пара подходит, добавляем в решение.
            solution.push_back(A[l]);
            solution.push_back(A[r]);
            l++;
            r--;
        } else if (current_sum < S) {
            // A[l] слишком мал, его нужно отбросить.
            l++;
        } else { // current_sum > S
            // A[r] слишком велик, его нужно отбросить.
            r--;
        }
    }

    // Проверка успешна, если мы набрали ровно N элементов.
    if (solution.size() == N) {
        return solution;
    }

    return {}; // Не удалось найти решение для этой суммы S.
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N, K;
    std::cin >> N >> K;

int M = N + K;
    std::vector<int> A(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i];
    }
    
    // В условии сказано "given a sorted sequence", но сортировка делает код надежнее.
    if (!std::is_sorted(A.begin(), A.end())) {
        std::sort(A.begin(), A.end());
    }

    // Генерируем кандидатов на сумму S (логика из подзадач 6 и 7)
    // Используем std::set для хранения только уникальных сумм.
    std::map<long long, int> candidate_sums;
    for (int i = 0; i <= K; ++i) {
        for (int j = M - 1 - K; j < M; ++j) {
            // Убедимся, что индексы не пересекаются и массив достаточно велик
            if (i < j) {
                candidate_sums[(long long)A[i] + A[j]]++;
            }
        }
    }
    

    // Проверяем каждого кандидата
    for (auto [S, cnt] : candidate_sums) {
        if (M > 4 * K && cnt < K) {
            continue;
        }
        std::vector<int> result = check(S, A, N);
        if (!result.empty()) {
            // Решение найдено!
            // Отсортируем для единообразного вывода и выведем результат.
            std::sort(result.begin(), result.end());
            for (int i = 0; i < result.size(); ++i) {
                std::cout << result[i] << (i == result.size() - 1 ? "" : " ");
            }
            std::cout << "\n";
            
            // Так как нужно найти любое решение, можно завершать работу.
            return 0;
        }
    }

    // Этот участок кода не должен быть достигнут, так как решение всегда существует.
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 9 / 9
• Subtask 3: 0 / 14
• Subtask 4: 15 / 15
• Subtask 5: 0 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13