Cod sursa(job #1340543)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 11 februarie 2015 21:27:58
Problema Subsir crescator maximal Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.66 kb
#include <stdio.h>
#include <stdlib.h>
int v[100002],poz[100002];
void quicksort(int p,int u,int a[],int b[])
{
    int pivot,j,i,aux,t;
    if(p<u)
    {
        pivot=a[(p+u)/2];
        i=p;
        j=u;
        while(i<=j)
        {
            while(a[i]<pivot && i<u)
                i++;
            while(a[j]>pivot && j>p)
                j--;
            if(i<=j){
                aux=a[i];
                a[i]=a[j];
                a[j]=aux;
                aux=b[i];
                b[i]=b[j];
                b[j]=aux;
                i++;
                j--;
            }
        }
        if(p<j)
            quicksort(p,j,a,b);
        if(i<u)
            quicksort(i,u,a,b);
    }
}
int main()
{
    int n,i,p,max,s,j,nr;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&v[i]);
        poz[i]=i;
    }
    quicksort(1,n,v,poz);
    max=0;
    s=0;
    for(i=1; i<=n;)
    {
        j=i+1;
        while(v[j]==v[i])
            j++;
        quicksort(i,j-1,poz,v);
        i=j;
    }
    for(i=1; i<=n;)
    {
        j=i+1;
        while(poz[j]>poz[i])
            j++;
        if(j-i>max)
        {
            max=j-i;
            s=i;
        }
        i=j;
    }
    nr=0;
    for(i=s; i<max+s;)
    {
        j=i+1;
        while(j<max+s && v[j]==v[i])
            j++;
        i=j;
        nr++;
    }
    printf("%d\n",nr);
    for(i=s; i<max+s;)
    {
        j=i+1;
        while(j<max+s && v[j]==v[i])
            j++;
        printf("%d ",v[i]);
        i=j;
    }

    return 0;
}