제출 #1317677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317677		tuncay_pasha	Table Tennis (info1cup20_tabletennis)	C++20	0 / 100	29 ms	8692 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++;
    sort(a.begin(), a.end());

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

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

    // candidate sums with global count
    unordered_map<int,int> global;
    global.reserve(10000);

    vector<int> tmp;
    tmp.reserve(m);

    // process per anchor
    for(int i = 0; i < LIM; i++){
        tmp.clear();
        int ai = a[i];

        for(int j = i + 1; j < m; j++){
            tmp.push_back(ai + a[j]);
        }

        sort(tmp.begin(), tmp.end());

        // take only local top ~10 sums
        for(int p = 0; p < (int)tmp.size(); ){
            int q = p;
            while(q < (int)tmp.size() && tmp[q] == tmp[p]) q++;

            int cnt = q - p;
            if(cnt >= 2) { // prune noise
                global[tmp[p]] += cnt;
            }
            p = q;
        }
    }

    // extract best global sums
    vector<pair<int,int>> cand;
    for(auto &e : global){
        cand.push_back({e.second, e.first});
    }

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

    // validate 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;
}

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