11462 - Age Sort

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shawon10
New poster
Posts: 4
Joined: Sun Feb 01, 2015 2:43 pm
Location: RUET
Contact:

Re: 11462 - Age Sort

Post by shawon10 » Tue Feb 03, 2015 6:24 pm

why Time Limit Exceed?

Code: Select all

#include <stdio.h>
int main()
{
    int n,*a,i,j,t;

    while(scanf("%d",&n)!=EOF)
    {
        a=(int*)malloc(sizeof(int)*n);
        if(n==0)
        {
            break;
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",(a+i));
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                if(*(a+i)>*(a+j))
                {
                      t=*(a+j);
                    *(a+j)=*(a+i);
                    *(a+i)=t;
                }
            }
        }
        for(i=0;i<n;i++)
        {
            printf("%d ",*(a+i));
        }
        printf("\n");
    }
    return 0;
}
Last edited by brianfry713 on Wed Feb 04, 2015 1:12 am, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11462 - Age Sort

Post by brianfry713 » Wed Feb 04, 2015 1:12 am

Read this thread.
Check input and AC output for thousands of problems on uDebug!

shawon10
New poster
Posts: 4
Joined: Sun Feb 01, 2015 2:43 pm
Location: RUET
Contact:

Re: 11462 - Age Sort

Post by shawon10 » Wed Feb 04, 2015 10:51 am

brianfry713 wrote:Read this thread.
Yes.. for 100000 this code is not running. but how can i fix Time Limit Exceed in this code?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11462 - Ages Sort

Post by brianfry713 » Wed Feb 04, 2015 8:21 pm

neilor wrote:Dears, only for couriously, there are here some performances tests that I can relate for this problem:

Método Execution time
bubleSort TLE (> 5 seconds)
Qsort Stl with cin / cout 1.072
Quicksort with scanf / printf 0.786 secs (maybe not so good qsort!?)
Mergesort with scanf / printf 0.656 secs (with a best mergesort)
qsort Stl [ sort(age,age + tam); ] 0.596 secs
Counting Sort (with vector) 0.473 secs (18 º world time)
Counting Sort (without vector) 0.456 secs
Counting Sort with fast input 0.343 seconds (13 º )
Counting Sort with fread/fwrite 0.204 seconds (10 º )
Counting Sort fread/fwrite optimized 0.156 (8º)
Counting Sort fread optimized /fwrite optimized 0.052 (2º) same that 1º mundial place.
Check input and AC output for thousands of problems on uDebug!

MI Sabic
New poster
Posts: 1
Joined: Tue Oct 06, 2015 8:01 am

Re: 11462 - Age Sort

Post by MI Sabic » Tue Oct 06, 2015 8:14 am

can anyone help me???
why TLE??

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int divide(int arr[], int start, int end)
{
    int pivot;
    if(start>=end)
        return ;
    else
    {
        pivot=sort(arr,start,end);
        divide(arr,start,pivot-1);
        divide(arr,pivot+1,end);
    }
}

int sort(int arr[], int start, int end)
{
    int i,j,pivot,rec=1;
    pivot=arr[start];
    i=start;
    j=end;
    while(i<j)
    {
        if(rec)
        {
            if(arr[j]<pivot)
            {
                arr[i]=arr[j];
                i++;
                rec=0;
            }
            else
                j--;
        }
        else
        {
            if(arr[i]>pivot)
            {
                arr[j]=arr[i];
                j--;
                rec=1;
            }
            else
                i++;
        }
    }
    arr[j]=pivot;
    return j;
}

int main()
{
    int i,j,n,temp,*arr;
    while(scanf("%d",&n)==1)
    {
        arr=malloc(n*sizeof(int));
        if(n==0)
            break;
        for(i=0; i<n; i++)
            scanf("%d",&arr[i]);
        divide(arr,0,n-1);
        for(i=0; i<n; i++)
        {
            printf("%d",arr[i]);
            if (i<(n-1))
                printf(" ");
        }
        printf("\n");
        free(arr);
    }
    return 0;
}

Post Reply

Return to “Volume 114 (11400-11499)”