Submission #3596975

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;

main(){
  int n; cin >> n;
  vll asc(n);
  for(int i=0;i<n;++i) cin >> asc[i];
  vll desc = asc;
  sort(asc.begin(),asc.end());
  sort(desc.begin(),desc.end(),greater<ll>());
  vll ans(n,-1);
  ans[(n-1)/2] = asc[0];
  int l = (n-1)/2 - 1; int r = l+2;
  int i;
  bool turn = 1;
  int posA =1, posD = 0;
  for(i=1;i<n-1;i+=2){
    //cout << l << " " << r << endl;
    //for(int j=0;j<n;++j) cout << ans[j] << " ";
    //cout << endl;
    if(turn){
      ans[r] = desc[posD]; ans[l] = desc[posD+1];
      posD+=2;
    }else{
      ans[r] = asc[posA]; ans[l] = asc[posA+1];
      posA+=2;
    }
    r++;l--;
    turn = !turn;
  }
  if(n%2==0){
    if(turn) ans[n-1] = desc[posD];
    else ans[n-1] = asc[posA];
  }
  //for(i=0;i<n;++i) cout << ans[i] << " ";
  //cout << endl;
  ll val = 0;
  for(i=0;i<n-1;++i){
    val += abs(ans[i] - ans[i+1]);
  }
  cout << val << endl;
}

Submission Info

Judge Result