1. // DA_serie03.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include "stdafx.h"
  5. #include <iostream>
  6. #include <string>
  7. #include <iostream>
  8. #include <string>
  9. using namespace std;
  10.  
  11.  
  12. static int currentsize=0;
  13. void merge(int in[], int l, int m, int r);
  14. void sort(int *in);
  15.  
  16. int main()
  17. {
  18. 	int testcases ;
  19. 	for ( cin >> testcases ; testcases > 0 ; testcases-- ) {
  20. 		int *values=NULL;
  21. 		cin >> currentsize;
  22. 		values = new int[currentsize];
  23. 		int element;
  24. 		cin >> element;
  25. 		int length;
  26. 		cin >> length;
  27. 		for (int i = 2; i<currentsize;i++) cin >> values[i-2];
  28.  
  29. 		int median = medianOfMedian(values,false);
  30. 		sort(values);
  31. 		int found = values[element];
  32.  
  33. 		cout << found << " "<<median << "\n";
  34. 		delete [] values;
  35. 	}
  36. 	//system("pause");
  37. 	return 0;
  38. }
  39.  
  40. static int medianOfMedian(int* in, bool second){
  41. 	int length = sizeof(in);
  42. 	if (length<6) return -1; //no medianofmedian, only a median
  43. 	// CHEAT? this is the real median of medians instead of again the median of medians of more groups of 5.
  44. 	if (second) {
  45. 		sort(in);
  46. 		return in[length/2];
  47. 	}
  48. 	int* currentgroup=new int[5]; //to save the groups of 5
  49. 	int nrmedians = (length%5==0)?length/5:length/5+1;
  50. 	int* medians=new int[nrmedians]; //to save all the medians
  51. 	/* loop through numbers, make groups of five, sort them and compute their medians*/
  52.  
  53. 	for (int s = 0;s<nrmedians;s++){
  54. 		int j=0;
  55. 		if (s==nrmedians-1) currentgroup= new int[length-s*5];
  56. 		while (j<5&&j+s*5<length) {
  57. 			currentgroup[j]=in[s*5+j];
  58. 			j++;
  59. 		}
  60. 		sort(currentgroup);
  61. 		if (j==5||j==4) medians[s]=currentgroup[2];
  62. 		else if (j==3||j==2) medians[s]=currentgroup[1];
  63. 		else medians[s]=currentgroup[0];
  64. 	}
  65. 	if (nrmedians<6) {
  66. 		sort(medians);
  67. 		if (nrmedians==5||nrmedians==4) return medians[2];
  68. 		else if (nrmedians==3||nrmedians==2) return medians[1];
  69. 		else return medians[0];
  70. 	} else return medianOfMedian(medians,true);
  71. }
  72.  
  73.  
  74. static void merge(int *in, int l, int m, int r) {
  75. 	int *out = new int[currentsize];
  76.  
  77. 	int i = l;
  78. 	int j = m + 1;
  79. 	int k = l;
  80. 	while (i <= m && j <= r) {
  81. 		// vergleiche von Folgeleementen
  82. 		if (in[i] < in[j]) {
  83. 			out[k] = in[i];
  84. 			i++;
  85. 		} else {
  86. 			out[k] = in[j];
  87. 			j++;
  88. 		}
  89. 		k++;
  90. 	}
  91. 	if (i > m) {
  92. 		for (int h = l; h < j; h++) {
  93. 			in[h] = out[h];
  94. 		}
  95. 		// 		for (int h = j; h<=r;h++){
  96. 		// 			out[h]=in[h];
  97. 		// 			k++;
  98. 		// 		}
  99. 	} else {
  100. 		for (int h = i; h <= m; h++) {
  101. 			out[k + h - i] = in[h];
  102. 		}
  103. 		for (int h = l; h <= r; h++) {
  104. 			in[h] = out[h];
  105. 		}
  106. 	}
  107.  
  108. 	delete [] out;
  109. }
  110.  
  111.  
  112. static void sort(int *in) {
  113. 	int ll = 0, rr = 0, mm = 0;
  114. 	int l = 0;
  115. 	int r = sizeof(in);
  116. 	do {
  117. 		rr = l - 1;
  118. 		while (rr < r) {
  119. 			ll = rr + 1;
  120. 			mm = ll;
  121. 			while (mm < r && in[mm + 1] > in[mm]) {
  122. 				mm++;
  123. 			}
  124. 			if (mm < r) {
  125. 				rr = mm + 1;
  126. 				while (rr < r && in[rr + 1] > in[rr]) {
  127. 					rr++;
  128. 				}
  129. 				merge(in, ll, mm, rr);
  130. 			} else {
  131. 				rr = mm;
  132. 			}
  133. 		}
  134.  
  135. 	} while (ll != l);
  136. }