week14- E. Score Distribution 3, Author Solution

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define MP make_pair
#define PB push_back
#define PII pair<int,int>
#define VPII vector<pair<int,int> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int SIZE = 200*1000+1;
VPII pp;
long long sum[SIZE];
int an[SIZE];
int main(){
    int N;
    scanf("%d",&N);
    pp.PB(MP(0,0));
    for(int i=1;i<=N;i++){
        int x;
        scanf("%d",&x);
        pp.PB(MP(x,i));
    }
    sort(pp.begin(),pp.end());
    for(int i=1;i<=N;i++){
        sum[i]=sum[i-1]+pp[i].F;
    }
    int ma=1,anL=1,anR=2;
    for(int i=N;i>ma;i--){
        int ll=1,rr=i-1;
        while(ll<rr){
            int mm=(ll+rr)/2;
            if(sum[(mm+i)/2]-sum[mm-1]>sum[i]-sum[(mm+i+1)/2])rr=mm;
            else ll=mm+1;
        }
        if(ma<i-ll+1){
            ma=i-ll+1;
            anL=ll;
            anR=i+1;
        }
    }
    int v=pp[(anL+anR)/2].first;
    for(int i=1;i<anL;i++)an[pp[i].second]=v;
    for(int i=anL;i<anR;i++)an[pp[i].second]=pp[i].first;
    for(int i=anR;i<=N;i++)an[pp[i].second]=v;
    for(int i=1;i<=N;i++)printf("%d%c",an[i]," \n"[i==N]);
    return 0;
}