PAM!#12251

PAM! (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

We only care about pairs that sum up to $k$ , We need to construct the longest sequence of integers where $a_{i} + a_{i + 1} = k$ a_i+a_{i+1}=k for the most number of indices $i$ on that sequence.

Firstly , we pick all distinct pairs $(x, y)$ that sum up to $k$ , where $cnt (x), cnt (y) \geq 1$ \text{cnt}(x),\text{cnt}(y) \ge 1 , the optimal construction will be $x, y, x, y, x, y, ...$ x,y,x,y,x,y,... where the length of it $min (cnt (x), cnt (y))$ \min(\text{cnt}(x),\text{cnt}(y)) , in the ideal case it'll be $⌊ m i n (cnt(x), cnt (y)) /2 ⌋ x, y, x, y, ..., x, y$ \underbrace{x,y,x,y,...,x,y}_{\lfloor \min(\text{cnt(x)},\text{cnt}(y))/2 \rfloor} however if we've if we've the frequencies forming different parties then we've to leave the one with extra element at the end , starting from the element with extra element.

We do the same for all pairs $(x, y)$ that's $x + y = k$ x+y=k , and the rest of elements are irrelevant so that they can be put in any order.

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

void solve(){
    int n,k;cin>>n>>k;
    vector<int>a(n);
    for(auto &i:a)cin>>i;
    map<int,int>mp;
    for(auto i:a)mp[i]++;
    set<pair<int,int>>pairs;
    for(auto i:a){
        if(mp[i]&&mp[k-i]){
            pairs.insert({i,k-i});
        }
    }
    vector<int>b;
    for(auto p:pairs){
        if(p.first==p.second){
            continue;
        }
        if(mp[p.first]>mp[p.second]){
            swap(p.first,p.second);
        }
        while(mp[p.first]>0){
            b.push_back(p.second);
            b.push_back(p.first);
            mp[p.second]--;
            mp[p.first]--;
        }
        while(mp[p.second]>0){
            b.push_back(p.second);
            mp[p.second]--;
        }
    }
    for(auto i:pairs){
        if(i.first==i.second){
            while(mp[i.first]){
                b.push_back(i.first);
                mp[i.first]--;
            }
        }
    }
    for(auto i:mp){
        while(mp[i.first]){
            b.push_back(i.first);
            mp[i.first]--;
        }
    }
    for(auto i:b){
        cout<<i<<" ";
    }
    cout<<"\n";
}


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

C++

Complexity $O (n lo g n)$ \mathcal{O}(n \log n).