oj.uz

Submission #355144

# Submission time Handle Problem Language Result Execution time Memory
355144 2021-01-22T09:29:22 Z valerikk Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 448 ms 33260 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 748 KB Output is correct
2 Correct 43 ms 3296 KB Output is correct
3 Correct 38 ms 4704 KB Output is correct
4 Correct 39 ms 4704 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 3168 KB Output is correct
2 Correct 38 ms 3296 KB Output is correct
3 Correct 48 ms 3296 KB Output is correct
4 Correct 40 ms 4704 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 5 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 14 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 364 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 41 ms 3260 KB Output is correct
3 Correct 43 ms 4704 KB Output is correct
4 Correct 40 ms 4704 KB Output is correct
5 Correct 41 ms 4704 KB Output is correct
6 Correct 38 ms 4704 KB Output is correct
7 Correct 40 ms 4704 KB Output is correct
8 Correct 43 ms 4704 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1008 KB Output is correct
2 Correct 448 ms 30060 KB Output is correct
3 Correct 390 ms 33260 KB Output is correct
4 Correct 277 ms 29164 KB Output is correct
5 Correct 146 ms 10752 KB Output is correct
6 Correct 72 ms 4744 KB Output is correct
7 Correct 251 ms 25836 KB Output is correct
8 Correct 250 ms 28140 KB Output is correct