MINK - Huyền thoại Lục Vân Tiên

Tác giả: hieult

Ngôn ngữ: C++

#include <stdio.h>
//#include <conio.h>
main()
{
long T,n,k,a[17001],left[17001],right[17001],r[17002],l[17002],f[17001];
scanf("%ld",&T);
for(long i=1;i<=T;i++)
  {
  scanf("%ld %ld",&n,&k);
  for(long j=1;j<=n;j++)
    scanf("%ld",&a[j]);
  long u=1;
  r[1]=1;
  while(r[u]!=n+1)
    {
    long t=r[u]+1;
    if(a[t]<a[r[u]])
      {
      for(long j=u;j>=1;j--)
        {
        if(a[t]<a[r[j]])
          {
          right[r[j]]=t-1;
          u--;
          }
        else  
          break;
        }
      u++;
      r[u]=t;  
      }
    else if(t==n)
      {
      for(long j=u;j>=1;j--)
        right[r[j]]=n;          
      break;
      }
    else
      {
      u++;
      r[u]=t;
      }
    }            
  right[n]=n;
  u=1;
  l[1]=n;
  //printf("%ld %ld %ld %ld",right[4],right[3],right[2],right[1]);
  while(l[u]!=0)
    {
    long t=l[u]-1;
    if(a[t]<a[l[u]])
      {
      for(long j=u;j>=1;j--)
        {
        if(a[t]<a[l[j]])
          {
          left[l[j]]=t+1;
          u--;
          }
        else  
          break;
        }
      u++;
      l[u]=t;  
      }
    else if(t==n)
      {
      for(long j=u;j>=1;j--)
        left[l[j]]=n;          
      break;
      }
    else
      {
      u++;
      l[u]=t;
      }
    }
  left[1]=1;  
  //printf("%ld %ld %ld",left[4],left[3],left[2]);              
  for(long j=1;j<=n;j++)
    {
    if(left[j]<j-k+1)
      left[j]=j-k+1;
    if(right[j]>j+k-1)
      right[j]=j+k-1;
    for(long t=left[j];t<=right[j]-k+1;t++)
      f[t]=a[j];
    }
  for(long j=1;j<=n-k+1;j++)
    printf("%ld ",f[j]);
  printf("\n");
  }
//getch();
}                                     
      

Download