제출 #1317685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317685		tuncay_pasha	Table Tennis (info1cup20_tabletennis)	C++20	100 / 100	67 ms	4928 KiB

tabletennis

/**
 * Problem: Table Tennis
 * * Approach:
 * 1. Identify that the subset must satisfy the property that pairs sum to a constant S.
 * 2. The outermost pair of the optimal subset determines S. Since at most K elements are removed,
 * the outermost pair must be formed by A[i] and A[M-1-j] where i + j <= K.
 * 3. Generate all possible candidate sums S from these valid outer pairs.
 * 4. For each S, run a greedy 2-pointer check to see if we can find N/2 pairs summing to S
 * with at most K skips.
 * 5. Optimization: The greedy check aborts early (in O(K) steps) for invalid sums, ensuring
 * efficiency.
 */

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

using namespace std;

// Function to check if a specific sum S is valid
// If 'print' is true, it outputs the solution.
bool solve(long long S, int N, int K, const vector<long long>& A, bool print) {
    int L = 0;
    int R = (int)A.size() - 1;
    int skips = 0;
    
    vector<long long> res;
    if (print) {
        res.reserve(N);
    }
    
    while (L < R) {
        // Optimization: if we already exceeded K skips, abort.
        if (skips > K) return false;
        
        long long current_sum = A[L] + A[R];
        
        if (current_sum == S) {
            // Match found
            if (print) {
                res.push_back(A[L]);
                res.push_back(A[R]);
            }
            L++;
            R--;
        } else if (current_sum < S) {
            // Sum too small, A[L] cannot be paired, skip it
            skips++;
            L++;
        } else {
            // Sum too large, A[R] cannot be paired, skip it
            skips++;
            R--;
        }
    }
    
    // If pointers met at the same element, that element is unpaired and must be skipped
    if (L == R) {
        skips++;
    }
    
    if (skips <= K) {
        if (print) {
            // We might have collected more pairs than needed if K - skips > 0 allows extra pairs.
            // We only need exactly N elements (N/2 pairs).
            if (res.size() > N) {
                res.resize(N);
            }
            
            // The output must be sorted
            sort(res.begin(), res.end());
            
            for (int i = 0; i < N; ++i) {
                cout << res[i] << (i == N - 1 ? "" : " ");
            }
            cout << "\n";
        }
        return true;
    }
    
    return false;
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (cin >> N >> K) {
        int M = N + K;
        vector<long long> A(M);
        for (int i = 0; i < M; ++i) {
            cin >> A[i];
        }
        
        // Generate candidate sums
        // The outermost pair of the solution must be (A[i], A[M-1-j])
        // such that the number of dropped elements before them (i) + after them (j) is <= K.
        vector<long long> candidates;
        candidates.reserve((K + 1) * (K + 1));
        
        for (int i = 0; i <= K; ++i) {
            for (int j = 0; j <= K - i; ++j) {
                candidates.push_back(A[i] + A[M - 1 - j]);
            }
        }
        
        // Remove duplicates to avoid redundant checks
        sort(candidates.begin(), candidates.end());
        candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
        
        // Check each candidate
        for (long long S : candidates) {
            // First check without building the result vector (faster)
            if (solve(S, N, K, A, false)) {
                // If valid, run again to print
                solve(S, N, K, A, true);
                return 0;
            }
        }
    }
    
    return 0;
}

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