#include <iostream>
#include <time.h>
using namespace std;
 
#define min(a,b) ((a) < (b) ? (a) : (b))
 
int numswaps = 0;
void swap(int a[], int i, int j)
{
	int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
	numswaps++;
}
 
int select(int a[], int k, int l, int r);
void printArr(int a[], int l, int r)
{
	for (int i=l; i<=r; ++i)
		printf("%i ", a[i]);
	printf("\n");
}
 
void insertSort(int a[], int l, int r)
{
	for (int i=l+1; i<=r; ++i)
	{
		int j = i;
		while (j>l && a[j] < a[j-1])
		{
			swap(a,j,j-1);
			j--;
		}
	}
}
 
int medMed(int a[], int l, int r)
{
	int j = l-1;
	for (int i=l; i<=r; i+=5)
	{
		int rr = min(i+4,r);
		insertSort(a,i,rr);
		swap(a,++j,(i+rr)/2);
	}
	int m = (j-l)/2+1;
	return select(a,m,l,j);
}
 
int partition(int a[], int l, int r)
{
	int pp = medMed(a,l,r);
	swap(a[pp],a[r]);
	int p = a[r];
	int i = l-1;
	for (int j=l; j<r; ++j)
		if (a[j] < p)
			swap(a,++i,j);
	swap(a,++i,r);
	return i;
}
 
int numselect = 0;
int select(int a[], int k, int l, int r)
{
	numselect++;
	if (l>r) { printf("error l>r\n"); exit(-1); }
	if (l==r) { if (k == 1) return l; printf("error k!=1"); exit(-1); }
	int p = partition(a,l,r);
	if (k<p+1-l) select(a,k,l,p-1);
	else if (k>p+1-l) select(a,k-(p+1-l),p+1,r);
	else return p;
}
 
const int SIZE = 10000000;
int arr[SIZE+1];
void  generate()
{
	numswaps = 0;
	numselect = 0;
	for (int i=0; i<=SIZE; ++i)
		arr[i] = rand();
}
void verify(int s)
{
	int last = -1;
	for (int i=1; i<=s; ++i)
	{
		int cur = select(arr,i,0,s);
		if (last > cur) { printf("invalid"); exit(-2); }
		last = cur;
	}
}
int main() {
	clock_t begin = clock();
	for (int i=1; i<=SIZE; i*=10)
	{
		generate();
		select(arr,(1+i)/2,1,i);
		printf("#swaps for finding median of %8i elements: %8i (%i)\n", i, numswaps, numselect);
	}
	clock_t end = clock();
	double time = (double)(end - begin) / CLOCKS_PER_SEC;
	printf("Total time: %f", time);
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dGltZS5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBtaW4oYSxiKSAoKGEpIDwgKGIpID8gKGEpIDogKGIpKQoKaW50IG51bXN3YXBzID0gMDsKdm9pZCBzd2FwKGludCBhW10sIGludCBpLCBpbnQgaikKewoJaW50IHRtcCA9IGFbaV07IGFbaV0gPSBhW2pdOyBhW2pdID0gdG1wOwoJbnVtc3dhcHMrKzsKfQoKaW50IHNlbGVjdChpbnQgYVtdLCBpbnQgaywgaW50IGwsIGludCByKTsKdm9pZCBwcmludEFycihpbnQgYVtdLCBpbnQgbCwgaW50IHIpCnsKCWZvciAoaW50IGk9bDsgaTw9cjsgKytpKQoJCXByaW50ZigiJWkgIiwgYVtpXSk7CglwcmludGYoIlxuIik7Cn0KCnZvaWQgaW5zZXJ0U29ydChpbnQgYVtdLCBpbnQgbCwgaW50IHIpCnsKCWZvciAoaW50IGk9bCsxOyBpPD1yOyArK2kpCgl7CgkJaW50IGogPSBpOwoJCXdoaWxlIChqPmwgJiYgYVtqXSA8IGFbai0xXSkKCQl7CgkJCXN3YXAoYSxqLGotMSk7CgkJCWotLTsKCQl9Cgl9Cn0KCmludCBtZWRNZWQoaW50IGFbXSwgaW50IGwsIGludCByKQp7CglpbnQgaiA9IGwtMTsKCWZvciAoaW50IGk9bDsgaTw9cjsgaSs9NSkKCXsKCQlpbnQgcnIgPSBtaW4oaSs0LHIpOwoJCWluc2VydFNvcnQoYSxpLHJyKTsKCQlzd2FwKGEsKytqLChpK3JyKS8yKTsKCX0KCWludCBtID0gKGotbCkvMisxOwoJcmV0dXJuIHNlbGVjdChhLG0sbCxqKTsKfQoKaW50IHBhcnRpdGlvbihpbnQgYVtdLCBpbnQgbCwgaW50IHIpCnsKCWludCBwcCA9IG1lZE1lZChhLGwscik7Cglzd2FwKGFbcHBdLGFbcl0pOwoJaW50IHAgPSBhW3JdOwoJaW50IGkgPSBsLTE7Cglmb3IgKGludCBqPWw7IGo8cjsgKytqKQoJCWlmIChhW2pdIDwgcCkKCQkJc3dhcChhLCsraSxqKTsKCXN3YXAoYSwrK2kscik7CglyZXR1cm4gaTsKfQoKaW50IG51bXNlbGVjdCA9IDA7CmludCBzZWxlY3QoaW50IGFbXSwgaW50IGssIGludCBsLCBpbnQgcikKewoJbnVtc2VsZWN0Kys7CglpZiAobD5yKSB7IHByaW50ZigiZXJyb3IgbD5yXG4iKTsgZXhpdCgtMSk7IH0KCWlmIChsPT1yKSB7IGlmIChrID09IDEpIHJldHVybiBsOyBwcmludGYoImVycm9yIGshPTEiKTsgZXhpdCgtMSk7IH0KCWludCBwID0gcGFydGl0aW9uKGEsbCxyKTsKCWlmIChrPHArMS1sKSBzZWxlY3QoYSxrLGwscC0xKTsKCWVsc2UgaWYgKGs+cCsxLWwpIHNlbGVjdChhLGstKHArMS1sKSxwKzEscik7CgllbHNlIHJldHVybiBwOwp9Cgpjb25zdCBpbnQgU0laRSA9IDEwMDAwMDAwOwppbnQgYXJyW1NJWkUrMV07CnZvaWQgIGdlbmVyYXRlKCkKewoJbnVtc3dhcHMgPSAwOwoJbnVtc2VsZWN0ID0gMDsKCWZvciAoaW50IGk9MDsgaTw9U0laRTsgKytpKQoJCWFycltpXSA9IHJhbmQoKTsKfQp2b2lkIHZlcmlmeShpbnQgcykKewoJaW50IGxhc3QgPSAtMTsKCWZvciAoaW50IGk9MTsgaTw9czsgKytpKQoJewoJCWludCBjdXIgPSBzZWxlY3QoYXJyLGksMCxzKTsKCQlpZiAobGFzdCA+IGN1cikgeyBwcmludGYoImludmFsaWQiKTsgZXhpdCgtMik7IH0KCQlsYXN0ID0gY3VyOwoJfQp9CmludCBtYWluKCkgewoJY2xvY2tfdCBiZWdpbiA9IGNsb2NrKCk7Cglmb3IgKGludCBpPTE7IGk8PVNJWkU7IGkqPTEwKQoJewoJCWdlbmVyYXRlKCk7CgkJc2VsZWN0KGFyciwoMStpKS8yLDEsaSk7CgkJcHJpbnRmKCIjc3dhcHMgZm9yIGZpbmRpbmcgbWVkaWFuIG9mICU4aSBlbGVtZW50czogJThpICglaSlcbiIsIGksIG51bXN3YXBzLCBudW1zZWxlY3QpOwoJfQoJY2xvY2tfdCBlbmQgPSBjbG9jaygpOwoJZG91YmxlIHRpbWUgPSAoZG91YmxlKShlbmQgLSBiZWdpbikgLyBDTE9DS1NfUEVSX1NFQzsKCXByaW50ZigiVG90YWwgdGltZTogJWYiLCB0aW1lKTsKCXJldHVybiAwOwp9