Spojで期限を超過しました

Question

この問題を解決しようとしていますhttp://www.spoj.com/problems/TSORT/ このエラーの制限時間を超過しました。 私のコードは私のコンピュータ上で正しくコンパイルしてソートしますが、私がスポイジに提出すると、このエラーが返されます。

#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; 

} 

Answer 1

次提案のコードはきれいにコンパイルし、

警告をリンク：それは私がテストしていないのOPアルゴリズムを使用しています。コードを高速化するための

：

1. ではなく 'FASTREAD（）' 関数を使用して '（scanf関数）'
2. 'はfastWrite（）関数ではなく、 'のprintf（）' を使用
3. 3排他的論理和（マクロなど）文よりもむしろ「スワップ（）」関数
4. 設定機能「インライン」コンパイラがそれを可能にする場合
5. が使用する「getchar_unlocked（）」、「putchar_unlocked（）を使用し'stdio.hよりずっと遅い重複数出力にこのコードブロックを排除する

   #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 
   

   ：「GETCHAR（）、および 'のputchar（）'

、現在提案されているコード

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

を置き換えることができますwith：

// 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]; 
     } 
    }