Selecting kids for a Christmas play with similar heights
Time is mostly spent in I/O

I played with your program and found that most of the time was spent doing I/O.  However, from your comments, it appears you already improved your I/O so that your best solution is now 0.02 seconds instead of 0.05 seconds.

I took your improved I/O code and took it one step further.  What I did was read the entire input into a buffer using a single fread(), and then instead of using getchar_unlocked(), I just advanced a pointer through the buffer using *p++.

Why is *p++ faster than getchar_unlocked()?  Here is what getchar_unlocked() does (not exactly but something close to this):

char getchar_unlocked()
{
    if (stdin.ptr &gt;= stdin.buffer_len) {
        refill_stdin_buffer();
        stdin.ptr = 0;
    }
    return stdin.buffer[stdin.ptr++];
}


So for every character you read, it does a check to see if it needs to reload the buffer.  If you read the entire input from stdin to a local buffer, you are essentially skipping and end of buffer check for each character you read.

Update: Later I found that my I/O changes didn't matter.  Both yours and mine were able to achieve 0.00 time, as long as radix sort was used (see next section).

Radix sort

Radix sort is 0.02 seconds faster than std::sort for this test.  I know because I tried it both ways.  First I tried radix sort, which took 0.00 seconds overall.  Then I replaced radix sort with std::sort and got 0.02 seconds.

In general, radix sort should be faster than quicksort for large arrays of integers.  The radix sort I used operates on bytes at a time, so for 32-bit integers it uses exactly 4 rounds.  On each round it does a counting pass followed by a rearranging pass.  So in total, it does approximately \$8n\$ operations to sort an array of \$n\$ integers, plus a fixed overhead of 1024 operations to deal with the buckets.

From my own testing, I found that radix sort is 5x faster than std::sort for sorting arrays of 10 million integers.  For 20000 integers, it is around 4x faster.

The final program, which achieved 0.00 seconds

Here is my program.  You can see in the SPOJ status that I got 0.00 seconds with it.  FYI, my first entry was a C program that got 0.00 seconds, but I changed it to the following C++ program:

#include &lt;bits/stdc++.h&gt;
#include &lt;cstdio&gt;

#define MAX                20000

// 30 testcases, 11 characters per number, 20000 numbers
char buf[MAX*11*30];
int array    [MAX];
int arrayTemp[MAX];

static inline int readInt(char **pPtr)
{
    char *p   = *pPtr;
    int   ret = 0;
    char  c   = *p++;

    while (c &lt; '0')
        c = *p++;
    do {
        ret = (ret &lt;&lt; 3) + (ret &lt;&lt; 1) + c - 48;
        c   = *p++;
    } while (c &gt;= '0');

    *pPtr = p;
    return ret;
}

void radixsort(int *a, int len)
{
    int *space       = arrayTemp;
    int *current     = a;
    int *scratch     = space;
    int *tmp         = NULL;
    int  radixByte   = 0;
    int  i           = 0;
    int  bucket[256];

    // Iterate once per byte.
    for (radixByte=0;radixByte&lt;4;radixByte++) {
        int shift = (radixByte &lt;&lt; 3);
        memset(bucket, 0, sizeof(bucket));

        // Count how many of each byte.
        for (i=0;i&lt;len;i++)
            bucket[(current[i] &gt;&gt; shift) &amp; 0xff]++;

        // Change bucket to be cumulative count.
        for (i=1;i&lt;256;i++)
            bucket[i] += bucket[i-1];

        // Copy from current to scratch, using bucket counts.
        for (i=len-1;i&gt;=0;i--)
            scratch[--bucket[(current[i] &gt;&gt; shift) &amp; 0xff]] = current[i];

        // Switch arrays
        tmp     = current;
        current = scratch;
        scratch = tmp;
    }
}

int main(void)
{
    char *p = buf;
    fread(buf, 1, sizeof(buf), stdin);

    int t = readInt(&amp;p);
    while (t-- &gt; 0) {
        int n = readInt(&amp;p);
        int k = readInt(&amp;p);

        for (int i = 0; i &lt; n; i++)
            array[i] = readInt(&amp;p);

        if (k == 1) {
            puts("0");
            continue;
        }

        radixsort(array, n);

        int diff = INT_MAX;
        n -= k;
        k--;
        for (int i = 0; i &lt;= n; i++) {
            int newDiff = array[i+k] - array[i];
            if (newDiff &lt; diff)
                diff = newDiff;
        }
        printf("%d\n", diff);
    }
    return 0;
}