Submission #1137916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137916		_unknown_2010	Table Tennis (info1cup20_tabletennis)	C++20	100 / 100	121 ms	4292 KiB

tabletennis

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#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;
// template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template<typename T> using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int int64_t
// #define vi vector
// #define ss second
// #define ff first
#define TESTCASES
// #define all(x) (x).begin(), (x).end()
// const int mod = 1E9+7;
// const int MAXN=200000;
// const int inf=1e18;

void solution(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n+k);
    for(auto &x:a){
        cin >> x;
    }
    vector<int> v;
    for(int i=n+k-1; i>=n-1; i--){
        for(int j=0; j<=k; j++){
            if(j>=i)break;
            int l=j,r=i,c=0;
            vector<int> ans;
            while(l<r && c<=k){
                if(ans.size()==n)break;
                if(a[l]+a[r]==a[i]+a[j]){
                    ans.push_back(a[l]);
                    ans.push_back(a[r]);
                    l++,r--;
                }
                else if(a[l]+a[r]<a[i]+a[j])l++,c++;
                else r--,c++;
            }
            if(ans.size()==n){
                sort(ans.begin(), ans.end());
                for(auto x:ans)cout << x << ' ';
                return;
            }
        }
    }
    // debug(v);
    bool d=0;
    auto calc = [&](int x) -> void {
        map<int,int> mp;
        for(auto x:a)mp[x]++;
        vector<int> ans;
        for(int i=n+k-1; i>=0; i--){
            if(ans.size()==n)break;
            if(mp[a[i]]==1 && mp[x-a[i]]==1){
                ans.push_back(a[i]);
                ans.push_back(x-a[i]);
                mp[a[i]]=0;
                mp[x-a[i]]=0;
            }
        }
        if(ans.size()==n){
            sort(ans.begin(),ans.end());
            d=1;
            for(auto x:ans)cout << x << ' ';
            return;
        }
    };
    for(auto x:v){
        if(d)return;
        calc(x);
    }
}
int32_t main(){
    // clock_t tStart = clock();
    #ifdef khos
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    #ifdef TESTCASES
        // cin >> q;
    #endif
    while(q--) {
        solution();
        cout << '\n';
    }
    // cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}

• 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