제출 #1317674

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

tabletennis

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    int m = n + k;

    vector<int> a(m);
    for(int i = 0; i < m; i++) cin >> a[i];

    if(k == 1) k++;

    int LIM = min(m, 2 * k);

    // collect sums
    vector<int> sums;
    sums.reserve((long long)LIM * m);

    for(int i = 0; i < LIM; i++){
        for(int j = i + 1; j < m; j++){
            sums.push_back(a[i] + a[j]);
        }
    }

    // sort sums
    sort(sums.begin(), sums.end());

    // extract most frequent sums
    vector<pair<int,int>> cand; // {count, sum}
    for(int i = 0; i < (int)sums.size(); ){
        int j = i;
        while(j < (int)sums.size() && sums[j] == sums[i]) j++;
        cand.push_back({j - i, sums[i]});
        i = j;
    }

    sort(cand.rbegin(), cand.rend());
    if((int)cand.size() > 100) cand.resize(100);

    // build frequency of values
    unordered_map<int,int> freq;
    freq.reserve(m * 2);
    for(int x : a) freq[x]++;

    // try candidates
    for(auto [_, S] : cand){
        vector<int> res;
        res.reserve(n);

        for(int x : a){
            int y = S - x;
            if(y != x){
                if(freq.count(y)) res.push_back(x);
            }else{
                if(freq[x] > 1) res.push_back(x);
            }
            if((int)res.size() > n) break;
        }

        if((int)res.size() == n){
            for(int x : res) cout << x << ' ';
            cout << '\n';
            return 0;
        }
    }

    return 0;
}
// test ucun btw :D

• 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: 0 / 13