Advertisement
Guest User

Untitled

a guest
Oct 25th, 2015
783
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Size 500005
  4.  
  5. int N;
  6. int s[Size];
  7. bool d[Size];
  8. int cnt = 0;
  9.  
  10. void solve(){
  11.     int i = 1,st = 1,tt;
  12.     while(i<N-1){
  13.         while(i<N-1 && d[i] != true){
  14.             i++;
  15.         }
  16.         if(i>=N-1) return;
  17.         tt = st = i;
  18.         while(tt<N-1){
  19.             if(d[tt] != true){
  20.                 break;
  21.             }
  22.             tt++;
  23.         }
  24.         tt--;
  25.         if(st == tt){
  26.             s[st] = s[st-1];
  27.             cnt = max(cnt,1);
  28.         }else{
  29.             int dif = tt-st+1;
  30.             if(s[st-1] == s[tt+1]){
  31.                 int ch = s[st-1];
  32.                 cnt = max(cnt, (dif+1)/2);
  33.                 for(int i = st;i<=tt;i++){
  34.                     s[i] = ch;
  35.                 }
  36.             }else{
  37.                 int ch = s[st-1];
  38.                 cnt = max(cnt,dif);
  39.                 for(int i = st;i<=tt;i++){
  40.                     s[i] = ch;
  41.                 }
  42.             }
  43.         }
  44.         i = tt+1;
  45.     }
  46. }
  47.  
  48. int main() {
  49.     cin >> N;
  50.     for(int i = 0;i<N;i++){
  51.         scanf("%d",&s[i]);
  52.     }
  53.     memset(d,false,sizeof(d));
  54.     for(int i = 1;i<N-1;i++){
  55.         if(s[i-1] == s[i+1] && s[i] != s[i-1]){
  56.             d[i] = true;
  57.         }
  58.     }
  59.     solve();
  60.     printf("%d\n",cnt);
  61.     printf("%d",s[0]);
  62.     for(int i = 1;i<N;i++) printf(" %d",s[i]);
  63.     printf("\n");
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement