Submission #1145162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145162		Robert_junior	Table Tennis (info1cup20_tabletennis)	C++20	87 / 100	3077 ms	376304 KiB

tabletennis

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e5 + 7;
int a[N];
unordered_map<int, int>mp;
map<int, vector<int>>g;
void solve(){
    int n, k;
    cin>>n>>k;
    vector<int>v;
    for(int i = 1; i <= n + k; i++){
        cin>>a[i];
        v.pb(a[i]);
        g[a[i]].pb(i);
        mp[a[i]]++;
    }
    sort(a + 1, a + n + k + 1);
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    for(int i = 1; i <= n + k; i++){
        a[i] = upper_bound(all(v), a[i]) - v.begin();
    }
    for(int i = 1; i <= k + 1; i++){
        for(int j = n + k; j >= n - 1; j--){
            int x = v[a[i] - 1] + v[a[j] - 1];
            int cnt = 0;
            for(auto it : v){
                if(it > x) cnt += mp[it];
                else{
                    cnt += max(0, mp[it] - mp[x - it]);
                    if(cnt > k) break;
                }
            }
            if(cnt > k) continue;
            vector<int>pos;
            for(int l = 1; l <= v.size(); l++){
                if(pos.size() >= n) continue;
                if(v[a[l] - 1] >= x) continue;
                int ok = v[a[l] - 1], ok1 = x - v[a[l] - 1];
                if(ok == ok1){
                    if(mp[ok] >= 2){
                        pos.pb(g[ok].back());
                        g[ok].pop_back();
                        pos.pb(g[ok].back());
                        g[ok].pop_back();
                        mp[ok] -= 2;
                    }
                }
                else{
                    if(mp[ok] > 0 && mp[ok1] > 0){
                        pos.pb(g[ok].back());
                        g[ok].pop_back();
                        pos.pb(g[ok1].back());
                        g[ok1].pop_back();
                        mp[ok]--;
                        mp[ok1]--;
                    }
                }
            }
            sort(all(pos));
            for(auto it : pos){
                cout<<v[a[it] - 1]<<' ';
            }
            return;
        }
    }
}
signed main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

• 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: 0 / 13