oj.uz

답안 #696594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696594 2023-02-07T00:50:44 Z hazzle Table Tennis (info1cup20_tabletennis) C++17
29 / 100
 3000 ms 10136 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

mt19937 rng((uint64_t) new char);

int solve(){
        int n, k;
        cin >> n >> k;
        int z = n + k;
        vec <int> a(z);
        for (auto &i: a) cin >> i;
        set <int> s(all(a));

        auto get_ans = [&](int x){
                vec <int> ans;
                for (int i = 0; i < z; ++i){
                        if (2 * a[i] != x && s.find(x - a[i]) != s.end() && n){
                                ans.push_back(a[i]);
                                ans.push_back(x - a[i]);
                                s.erase(a[i]), s.erase(x - a[i]), n -= 2;
                        }
                }
                sort(all(ans));
                for (auto &i: ans) cout << i << " ";
                exit(0);
        };

        if (n <= k){
                for (int i = 0; i < z; ++i){
                        for (int j = i + 1; j < z; ++j){
                                int x = a[i] + a[j];
                                int cnt = 0;
                                for (int l = 0; l < z; ++l){
                                        cnt += 2 * a[l] != x && s.find(x - a[l]) != s.end();
                                }
                                if (cnt >= n) get_ans(x);
                        }
                }
                return 0;
        }
        shuffle(all(a), rng);
        while(true){
                int ai = a[rng() % z];
                for (auto &aj: a){
                        int x = ai + aj;
                        int cnt = 0;
                        for (int i = 0; i < min(z, 3 * k); ++i){
                                cnt += 2 * a[i] != x && s.find(x - a[i]) != s.end();
                        }
                        if (cnt > 2 * k) get_ans(x);
                }
        }
        return 0;
}

signed main(){
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int tst = 1; //cin >> tst;
        while(tst--) solve();
        return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 1492 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 10056 KB Output is correct
2 Correct 301 ms 10112 KB Output is correct
3 Correct 271 ms 10136 KB Output is correct
4 Correct 186 ms 10072 KB Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 758 ms 10060 KB Output is correct
3 Correct 484 ms 10120 KB Output is correct
4 Correct 495 ms 10076 KB Output is correct
5 Correct 807 ms 10116 KB Output is correct
6 Incorrect 127 ms 10048 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 3094 ms 7960 KB Time limit exceeded
3 Halted 0 ms 0 KB -