Submission #697216

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
697216	2023-02-08T23:31:29 Z	hazzle	Table Tennis (info1cup20_tabletennis)	C++17	91 / 100	694 ms	4036 KB

tabletennis

#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;

        auto check = [&](int x){
                int pl = 0, pr = z - 1;
                vec <int> ans;
                while(pl < pr && sz(ans) < n){
                        if (a[pl] + a[pr] == x){
                                ans.push_back(a[pl]);
                                ans.push_back(a[pr]);
                                ++pl, --pr;
                        }
                        else if (a[pl] + a[pr] < x) ++pl;
                        else --pr;
                }
                if (sz(ans) == n){
                        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){
                                check(a[i] + a[j]);
                        }
                }
                assert(false);
        }
        int j = rng() % z;
        int l = max(0, z - j - k - 20), r = min(z, z - j + k + 20);
        for (int i = l; i < r; ++i){
                check(a[i] + a[j]);
        }
        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
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	788 KB	Output is correct
2	Correct	48 ms	3092 KB	Output is correct
3	Correct	45 ms	3008 KB	Output is correct
4	Correct	55 ms	3212 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	3116 KB	Output is correct
2	Correct	36 ms	3100 KB	Output is correct
3	Correct	35 ms	3096 KB	Output is correct
4	Correct	34 ms	3124 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #5
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Unexpected end of file - int32 expected
2	Halted	0 ms	0 KB	-

Subtask #6
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	74 ms	3088 KB	Output is correct
3	Correct	36 ms	3016 KB	Output is correct
4	Correct	39 ms	2988 KB	Output is correct
5	Correct	38 ms	3048 KB	Output is correct
6	Correct	46 ms	4036 KB	Output is correct
7	Correct	37 ms	3024 KB	Output is correct
8	Correct	44 ms	3112 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	694 ms	3080 KB	Output is correct
3	Correct	46 ms	3016 KB	Output is correct
4	Correct	162 ms	3076 KB	Output is correct
5	Correct	78 ms	3016 KB	Output is correct
6	Correct	52 ms	4036 KB	Output is correct
7	Correct	160 ms	3080 KB	Output is correct
8	Correct	162 ms	3096 KB	Output is correct

Submission #697216

Compilation message