document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <bits/stdc++.h>
  2. #define SZ(X) ((int)(X).size())
  3. #define MP make_pair
  4. #define PB push_back
  5. #define PII pair<int,int>
  6. #define VPII vector<pair<int,int> >
  7. #define F first
  8. #define S second
  9. typedef long long LL;
  10. using namespace std;
  11. const int SIZE = 200*1000+1;
  12. VPII pp;
  13. long long sum[SIZE];
  14. int an[SIZE];
  15. int main(){
  16.     int N;
  17.     scanf("%d",&N);
  18.     pp.PB(MP(0,0));
  19.     for(int i=1;i<=N;i++){
  20.         int x;
  21.         scanf("%d",&x);
  22.         pp.PB(MP(x,i));
  23.     }
  24.     sort(pp.begin(),pp.end());
  25.     for(int i=1;i<=N;i++){
  26.         sum[i]=sum[i-1]+pp[i].F;
  27.     }
  28.     int ma=1,anL=1,anR=2;
  29.     for(int i=N;i>ma;i--){
  30.         int ll=1,rr=i-1;
  31.         while(ll<rr){
  32.             int mm=(ll+rr)/2;
  33.             if(sum[(mm+i)/2]-sum[mm-1]>sum[i]-sum[(mm+i+1)/2])rr=mm;
  34.             else ll=mm+1;
  35.         }
  36.         if(ma<i-ll+1){
  37.             ma=i-ll+1;
  38.             anL=ll;
  39.             anR=i+1;
  40.         }
  41.     }
  42.     int v=pp[(anL+anR)/2].first;
  43.     for(int i=1;i<anL;i++)an[pp[i].second]=v;
  44.     for(int i=anL;i<anR;i++)an[pp[i].second]=pp[i].first;
  45.     for(int i=anR;i<=N;i++)an[pp[i].second]=v;
  46.     for(int i=1;i<=N;i++)printf("%d%c",an[i]," \\n"[i==N]);
  47.     return 0;
  48. }
');