#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void read_input(char *input, int *n, int *k, int **A)
{
FILE *fin = NULL;
int i;
fin = fopen(input, "r");
if (!fin) fprintf(stderr, "Could not open input file!\n"); // exit(1) ?
fscanf(fin, "%d%d", n, k);
*A = (int*)calloc((*n), sizeof(int));
if (!(*A)) fprintf(stderr, "Could not allocate memory for array!\n");
for (i = 0; i < (*n); ++i)
fscanf(fin,"%d", &((*A)[i]));
fclose(fin);
}
int Get(int *A, int st, int dr)
{
int i, j, pivot;
pivot = A[ ((rand()%(dr-st))+st) ];
i = st-1; j = dr+1;
while (1)
{
do { j--; } while (A[j] > pivot);
do { i++; } while (A[i] < pivot);
if (i < j)
{
A[i] ^= A[j];
A[j] ^= A[i];
A[i] ^= A[j];
}
else return j;
}
}
void find_kth(int *A, int p, int r, int i)
{
if (p == r)
return;
int q = Get(A, p, r);
int cnt = q-p+1;
if (i <= cnt)
find_kth(A, p, q, i);
else
find_kth(A, q+1, r, i-cnt);
}
void write_output(char *output, int n, int k, int *A)
{
FILE *fout = NULL;
fout = fopen(output, "w");
if (!fout) fprintf(stderr, "Could not open output file!\n");
find_kth(A, 0, n-1, k);
//int i;
//for (i = 0; i < n; ++i)
// printf ("%d ", *(A+i));
fprintf(fout, "%d\n", *(A+k-1));
fclose(fout);
}
int main(int argc, char **argv)
{
int N, K;
int *A = NULL;
char *in_file = "sdo.in";
char *out_file = "sdo.out";
/*
if (argc < 2)
{
fprintf(stderr, "Error ! Not enough parameters!\n");
exit(1);
}
*/
//in_file = argv[1];
read_input(in_file, &N, &K, &A);
srand(time(NULL));
//out_file = argv[2];
write_output(out_file, N, K, A);
free(A);
return 0;
}