Submission #355144

#	Time	Username	Problem	Language	Result	Execution time	Memory
355144		valerikk	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	448 ms	33260 KiB

tabletennis

#include <bits/stdc++.h>

using namespace std;

const int N = 150407;

int n, k;
int a[N];

void find_ans(int s) {
    int pos = n + k - 1;
    int cnt = 0;
    for (int i = 0; i < n + k; ++i) {
        while (pos > i && a[pos] + a[i] > s)
            --pos;
        if (pos <= i)
            break;
        if (a[i] + a[pos] == s) {
            ++cnt;
            --pos;
        }
    }
    if (2 * cnt >= n) {
        pos = n + k - 1;
        vector<int> left, right;
        for (int i = 0; i < n + k; ++i) {
            while (pos > i && a[pos] + a[i] > s)
                --pos;
            if (pos <= i)
                break;
            if (a[i] + a[pos] == s) {
                left.push_back(a[i]);
                right.push_back(a[pos]);
                --pos;
            }
        }
        reverse(right.begin(), right.end());
        for (int &x : left)
            cout << x << " ";
        for (int &x : right)
            cout << x << " ";
        exit(0);
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n + k; ++i)
        cin >> a[i];
    sort(a, a + n + k);
    vector<int> sums;
    if (n + k <= 4 * k) {
        for (int i = 0; i < n + k; ++i) {
            for (int j = 0; j < i; ++j) {
                sums.push_back(a[i] + a[j]);
            }
        }
    } else {
        map<int, int> mp;
        for (int i = 0; i < 2 * k; ++i) {
            for (int j = n + k - 1; j >= n + k - 2 * k; --j)
                ++mp[a[i] + a[j]];
        }
        for (auto [s, cnt] : mp) {
            if (cnt >= k)
                sums.push_back(s);
        }
    }
    for (int &s : sums)
        find_ans(s);
    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