Превышение лимита времени в Spoj

Я пытаюсь решить эту проблему http://www.spoj.com/problems/TSORT/ но я получаю эту ошибку, лимит времени превышен. Мой код правильно компилируется и сортируется на моем компьютере, но когда я отправляю его в spoj, он возвращает эту ошибку.

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



void random_shuffle(int arr[],unsigned long int tamanho)
{
    srand(time(NULL));
    int i, j, temp;
    for (i = tamanho - 1; i > 0; i--)
    {
        j = rand()%(i + 1);
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
int partion(int arr[], int p, int r)
{
    int pivotIndex = p + rand()%(r - p + 1); 
    int pivot;
    int i = p - 1;
    int j;
    pivot = arr[pivotIndex];
    swap(&arr[pivotIndex], &arr[r]);
    for (j = p; j < r; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }

    }
    swap(&arr[i+1], &arr[r]);
    return i + 1;
}

void quick_sort(int arr[], int p, int q)
{
    int j;
    if (p < q)
    {
        j = partion(arr, p, q);
        quick_sort(arr, p, j-1);
        quick_sort(arr, j+1, q);
    }
}
int main()
{
    int  *arr;
    int size = 0;
    int n;
    int i = 0;    

    scanf("%d",&size);
    arr = (int*)malloc(size*sizeof(int));

    while(scanf("%d",&n) != EOF){
        arr[i++] = n;
    }

    random_shuffle(arr,size); 
    quick_sort(arr, 0, size-1); 
    for (i = 0; i < size; i++)
         printf("%d\n", arr[i]);

    return 0;

}

c sorting quicksort

Bruno Justino Praciano 01.06.2017 источник

comment

Удалить random_shuffle(arr,size); ? - BLUEPIXY 01.06.2017

comment

Вопрос лучше подходит для проверки кода. - kaylum 01.06.2017

comment

Где вы устраняете дубликаты, как в требованиях? - Jonathan Leffler 01.06.2017

comment

размещенный код не компилируется! Среди прочего, в нем отсутствуют необходимые операторы #include для необходимых файлов заголовков. Вы ожидаете, что мы угадаем, какие файлы заголовков на самом деле включает ваш код? - user3629249 01.06.2017

comment

при вызове любой из функций выделения кучи (malloc, calloc, realloc) 1) возвращаемый тип — void*, который может быть назначен любому указателю. Приведение просто загромождает код, затрудняя его понимание, отладку и т. д. 2) всегда проверяйте (!=NULL) возвращаемое значение, чтобы убедиться, что операция прошла успешно - user3629249 01.06.2017

comment

@user3629249 user3629249 Извините, сейчас я включаю библиотеки. - Bruno Justino Praciano 01.06.2017

comment

SPOJ будет поставлять входные данные через стандартный ввод. поэтому функция: random_shuffle() может быть полностью исключена, как и заголовочный файл: time.h - user3629249 01.06.2017

comment

функция: malloc() работает МЕДЛЕННО, особенно по сравнению с объявлением области действия файла: size_t array[ 1000000 [; - user3629249 01.06.2017

Ответы (1)

arrow_upward
2
arrow_downward

следующий предложенный код чисто компилируется и связывается

Предостережение: он использует алгоритм OP, который я не тестировал.

для ускорения кода:

использует функцию «fastRead()», а не «scanf()»
использует функцию 'fastWrite()', а не 'printf()'
использует 3 оператора «исключающее ИЛИ» (в виде макроса), а не функцию «swap()»
устанавливает встроенные функции, когда это позволяет компилятор
использует 'getchar_unlocked()', 'putchar_unlocked()' из stdio.h, а не гораздо более медленные 'getchar() и 'putchar()'

а теперь предлагаемый код:

#include <stdio.h>


// prototypes
size_t partion( size_t arr[], size_t p, size_t r);
void quick_sort(size_t arr[], size_t p, size_t q);

void fastRead( size_t *a );
void fastWrite( size_t a );


size_t array[ 1000000 ];

#define swap( x, y ) \
        *(x) = *(x)^*(y);  \
        *(y) = *(y)^*(x);  \
        *(x) = *(x)^*(y);


inline void fastRead(size_t *a)
{
    int c=0;
    // note: 32 is space character
    while (c<33) c=getchar_unlocked();

    // initialize result value
    *a=0;

    // punctuation parens, etc are show stoppers
    while (c>47 && c<58)
    {
        *a = (*a)*10 + (size_t)(c-48);
        c=getchar_unlocked();
    }
    //printf( "%s, value: %lu\n", __func__, *a );
} // end function: fastRead


inline void fastWrite(size_t a)
{
    char snum[20];
    //printf( "%s, %lu\n", __func__, a );

    int i=0;
    do
    {
        // 48 is numeric character 0
        snum[i++] = (char)((a%10)+(size_t)48);
        a=a/10;
    }while(a>0);

    i=i-1; // correction for overincrement from prior 'while' loop

    while(i>=0)
    {
        putchar_unlocked(snum[i--]);
    }
    putchar_unlocked('\n');
} // end function: fastWrite


int main( void )
{
    size_t numEntries;
    fastRead(&numEntries);

    for( size_t i = 0; i<numEntries; i++ )
    {
        fastRead( &array[i++] );
    }

    quick_sort(array, 0, numEntries-1);

    for (size_t i = 0; i < numEntries; i++)
    {
         fastWrite( array[i]);
    }

    return 0;
} // end function: main


void quick_sort(size_t arr[], size_t p, size_t q)
{
    size_t j;

    if (p < q)
    {
        j = partion(arr, p, q);
        quick_sort(arr, p, j-1);
        quick_sort(arr, j+1, q);
    }
} // end function: quick_sort


size_t partion(size_t arr[], size_t p, size_t r)
{
    size_t pivotIndex = r >> 1;
    size_t pivot;
    size_t i = p - 1;
    size_t j;

    pivot = arr[pivotIndex];
    swap(&arr[pivotIndex], &arr[r]);

    for (j = p; j < r; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }

    }
    swap(&arr[i+1], &arr[r]);
    return i + 1;
} // end function: partion

чтобы исключить повторяющиеся числа, выведите этот кодовый блок:

    for (size_t i = 0; i < numEntries; i++)
    {
         fastWrite( array[i]);
    }

можно заменить на:

    // prime the 'pump'
    fastWrite( array[0] );
    size_t lastOutput = array[0];

    // 'pump' all the rest
    for (size_t i = 1; i < numEntries; i++)
    {
         if( lastOutput != array[i] )
         {
             fastWrite( array[i]);
             lastOutput = array[i];
         }
    }

user3629249 01.06.2017

comment

Спасибо, ваше решение мне очень помогло. - Bruno Justino Praciano; 02.06.2017

Превышение лимита времени в Spoj

Ответы (1)

Похожие вопросы