Envío 2552

Código

//
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MOD 1000000007
#define PI 3.14159265
#define EPS 1e-9
#define Pi acos(-1.0)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define forr(i,a,b) for(int i=(a); i<(b); i++)
#define clean(arr,val) memset(arr,val,sizeof(arr))
#define forn(i,n) forr(i,0,n)
#define PB push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vpll;

/*CODE START HERE*/

int n;
vi a;

//Quick sort
void quick(int l, int r){
    bool equal = true;
    forr(i,l,r){
        if(a[i] != a[i+1]){
            equal = false;
        }
    }
    if(equal) return;
    // cout << "BEGINNING L " << l << " R " << r << "\n";
    // forn(i,n) cout << a[i] << " ";
    // cout << "\n";
    if(l >= r)
        return;
    int indPivot = (rand()%(r-l+1))+l;
    // cout << "IND PIVOT " << indPivot << "\n";
    swap(a[l],a[indPivot]);
    int pivot = a[l];
    int p = l;
    for(int i = l+1; i <= r; i++){
        if(pivot >= a[i]){
            swap(a[++p],a[i]);
        }
        // forn(i,n) cout << a[i] << " ";
        // cout << "\n";
    }
    // forn(i,n) cout << a[i] << " ";
    // cout << "\n";
    // cout << "P " << p << "\n";
    // p--;
    swap(a[p],a[l]);
    if (l < (p-1))
        quick(l,p-1);
    if ((p+1) < r)
        quick(p+1,r);
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n;
    a.assign(n,0);
    forn(i,n) cin >> a[i];
    quick(0,n-1);
    cout << a[0];
    forr(i,1,n){
        cout << " " << a[i];
    }
    cout << "\n";
    return 0;
}