Submission #208507

#	Time	Username	Problem	Language	Result	Execution time	Memory
208507		tamionv	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	878 ms	2808 KiB

tabletennis

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

using ll = long long;
using cd = complex<double>;

auto mt = mt19937(12312);

int main(){
    int n, k;
    cin >> n >> k;

    vector<int> v(n + k);
    for(auto& x : v){
        cin >> x;
        assert(1 <= x && x <= 1e9);
    }

    vector<int> l;
    int the_sum = 0;
    l.reserve(n / 2);

    auto try_sum = [&](int s){
        int i = 0, j = n + k - 1;
        l.clear();
        the_sum = s;

        while(i < j && 2 * l.size() < n){
            if(v[i] + v[j] < s) ++i;
            else if(v[i] + v[j] > s) --j;
            else{
                l.push_back(v[i]);
                ++i, --j;
            }
        }

        if(2 * l.size() < n) l.clear();
    };

    do{
        int i = uniform_int_distribution<int>(0, n + k-1)(mt);
        for(int j = n - 1 - i; l.empty() && j <= n - 1 - i + 2 * k; ++j) {
            if(j < 0) continue;
            if(j >= n + k) break;
            try_sum(v[i] + v[j]);
        }
    } while(l.empty());

    for(auto x : l)
        cout << x << ' ';
    reverse(begin(l), end(l));
    for(auto x : l)
        cout << the_sum - x << ' ';

    return 0;
}

Compilation message (stderr)

tabletennis.cpp: In lambda function:
tabletennis.cpp:28:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < j && 2 * l.size() < n){
                        ~~~~~~~~~~~~~^~~
tabletennis.cpp:37:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(2 * l.size() < n) l.clear();
            ~~~~~~~~~~~~~^~~

• 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