Submission #807589

#	Time	Username	Problem	Language	Result	Execution time	Memory
807589		SorahISA	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	585 ms	5588 KiB

tabletennis

#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

// const int thres = -1;
const int thres = 320'000'000;

void solve() {
    int N, K; cin >> N >> K;
    
    vector<int> A(N+K);
    for (int &x : A) cin >> x;
    
    vector<int> chosen(N+K);
    auto chk = [&](int sum) -> int {
        fill(ALL(chosen), 0);
        int cnt = 0;
        for (int i = 0, j = N+K-1; i < j and cnt < N/2; ++i) {
            while (i < j and A[i] + A[j] > sum) --j;
            if (i < j and A[i] + A[j] == sum) ++cnt, chosen[i] = chosen[j] = 1, --j;
        }
        return cnt;
    };
    
    if (N * K * K <= thres) {
        for (int fr = 0; fr <= K; ++fr) {
            for (int bk = 0; fr+bk <= K; ++bk) {
                if (chk(A[fr] + A[N+K-1-bk]) == N/2) {
                    for (int i = 0; i < N+K; ++i) {
                        if (chosen[i]) cout << A[i] << " ";
                    }
                    cout << "\n";
                    return;
                }
            }
        }
    }
    else {
        while (true) {
            int x = rng() % (N + K);
            int L = N + K - 1 - max(x - K, int(0));
            int R = max(N - 1 - x, int(0));
            if (L > R) swap(L, R);
            
            for (int y = L; y <= R; ++y) {
                if (chk(A[x] + A[y]) == N/2) {
                    for (int i = 0; i < N+K; ++i) {
                        if (chosen[i]) cout << A[i] << " ";
                    }
                    cout << "\n";
                    return;
                }
            }
        }
    }
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

#endif

• 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