Submission #1866598

---

Source Code Expand

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

typedef long long ll;
typedef long double ld;

#define MAXI 200020
#define u(x, a, b) for(ll x = a; x < b; x++)
#define d(x, a, b) for(ll x = a; x > b; x--)

vector<ll> sub(vector<ll> in, ll le, ll ri){
    vector<ll> ans;
    if(le == ri){
        vector<ll> temp(1, 0);
        ans = temp;
        return ans;
    }
    u(two, le, ri){
        ans.push_back(in[two]);
    }
    return ans;
}

deque< pair<ll, ll> > greedy(vector<ll> in){
    deque< pair<ll, ll> > ans;
    ll s = in.size(), min1 = MAXI, tar1 = -1, min2 = MAXI, tar2 = -1;

    if(s == 1){
        ans.push_back(make_pair(MAXI, MAXI));
        return ans;
    }

    for(ll one = 0; one < s; one+=2){
        if(in[one] < min1){
            tar1 = one;
            min1 = in[one];
        }
    }
    for(ll one = tar1+1; one < s; one+=2){
        if(in[one] < min2){
            tar2 = one;
            min2 = in[one];
        }
    }
    ans.push_back(make_pair(min1, min2));
    vector<ll> v1 = sub(in, 0, tar1), v2 = sub(in, tar1+1, tar2), v3 = sub(in, tar2+1, s);
    deque< pair<ll, ll> > a1 = greedy(v1), a2 = greedy(v2), a3 = greedy(v3);
    ll y = MAXI;
    if(!a1.empty()){
        y = min(a1[0].first, y);
    }
    if(!a2.empty()){
        y = min(a2[0].first, y);
    }
    if(!a3.empty()){
        y = min(a3[0].first, y);
    }
    while(y < MAXI){
        if(y == a1[0].first){
            ans.push_back(a1[0]);
            a1.pop_front();
        }
        else if(y == a2[0].first){
            ans.push_back(a2[0]);
            a2.pop_front();
        }
        else{
            ans.push_back(a3[0]);
            a3.pop_front();
        }
        y = MAXI;
        if(!a1.empty()){
            y = min(a1[0].first, y);
        }
        if(!a2.empty()){
            y = min(a2[0].first, y);
        }
        if(!a3.empty()){
            y = min(a3[0].first, y);
        }
    }

    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, temp;
    cin >> n;
    vector<ll> arr;
    u(three, 0, n){
        cin >> temp;
        arr.push_back(temp);
    }
    deque< pair<ll, ll> > fin = greedy(arr);
    u(three, 0, n/2){
        cout << fin[three].first << ' ' << fin[three].second << ' ';
    }
}

Submission Info

Judge Result