oj.uz

답안 #807589

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807589 2023-08-04T19:47:12 Z SorahISA Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 585 ms 5588 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 992 KB Output is correct
2 Correct 22 ms 5588 KB Output is correct
3 Correct 21 ms 5572 KB Output is correct
4 Correct 21 ms 5588 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 5560 KB Output is correct
2 Correct 23 ms 5580 KB Output is correct
3 Correct 23 ms 5536 KB Output is correct
4 Correct 22 ms 5564 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 161 ms 5544 KB Output is correct
3 Correct 26 ms 5508 KB Output is correct
4 Correct 65 ms 5500 KB Output is correct
5 Correct 24 ms 5580 KB Output is correct
6 Correct 30 ms 5568 KB Output is correct
7 Correct 64 ms 5584 KB Output is correct
8 Correct 23 ms 5580 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 585 ms 5588 KB Output is correct
3 Correct 21 ms 5584 KB Output is correct
4 Correct 180 ms 5524 KB Output is correct
5 Correct 81 ms 5520 KB Output is correct
6 Correct 22 ms 5588 KB Output is correct
7 Correct 176 ms 5536 KB Output is correct
8 Correct 183 ms 5536 KB Output is correct