Concatenation.cpp

#define _cp(a,b) ((a)<(b))


//k+1's element. jilin's template
int kth_element(int n, int a[], int k){
    int l = 0, r = n-1, i, j, key;
    while (l < r){
        for (i=l-1, j = r+1, key = a[(i+j)>>1]; i < j; ){
            // j--, i++ at beginning of the loop is because, if i < j but a[i] == a[j] == key
            // then not progress any more. i, j points to end of range that is done.
            for (j--; _cp(key, a[j]); j--);
            for (i++; _cp(a[i], key); i++);
            if (i < j) swap(a[i], a[j]);
        }
        if (k > j) l = j+1;
        else r = j;
    }
    return a[k];
}