Submission #675147

#	Time	Username	Problem	Language	Result	Execution time	Memory
675147		vjudge1	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	347 ms	43192 KiB

tabletennis

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define iii pair<int, ii>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 300005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;

vector<int> cac;
map<int, int> mp;
int ans[maxN];

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k; n += k;
    for1(i, 1, n) cin >> a[i];
    if(n <= 2000){
        for1(i, 1, n) for1(j, i + 1, n) cac.pb(a[i] + a[j]);
        sort(all(cac)); cac.resize(unique(all(cac)) - cac.begin());
    }
    else{
        for1(i, 1, k * 2) for2(j, n, n - k * 2 + 1) mp[a[i] + a[j]]++;
        for(auto pr : mp) if(pr.se >= k) cac.pb(pr.fi);
    }
    for(int sum : cac){
        int l = 1, r = n;
        int cnt = 0;
        while(l != r){
            int fx = a[l] + a[r];
            if(fx == sum){
                ans[cnt++] = a[l];
                ans[cnt++] = a[r];
                --r;
            }
            else if(fx < sum) ++l;
            else --r;
        }
        if(cnt >= n - k){
            n -= k;
            sort(ans, ans + n);
            for1(i, 0, n - 1) cout << ans[i] << " ";
            cout << endl;
            exit(0);
        }
    }
}

• 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