fork(4) download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. inline void scan(int *a) {
  5.     register char c=0;
  6. 	while (c < 33)
  7. 		c = getchar_unlocked();
  8. 	*a = 0;	
  9. 	while (c > 33) {
  10. 		*a = *a * 10 + c - '0';
  11. 		c = getchar_unlocked();
  12. 	}
  13. }
  14.  
  15. void shellsort(char s[][10001][14], int n) {
  16. 	unsigned int gaps[] = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929};
  17.  
  18. 	int i, j, k;
  19. 	int gap;
  20. 	char temp[14];
  21. 	for (k = 10; k >= 0; k --) {
  22. 		gap = gaps[k];
  23. 		for (i = gap; i < n; i++) {
  24. 			strcpy(temp,s[0][i]);
  25. 			for (j = i; j >= gap && strcmp(s[0][j-gap], temp) > 0; j -= gap)
  26. 				strcpy(s[0][j], s[0][j-gap]);
  27. 			strcpy(s[0][j], temp);
  28. 		}
  29. 	}
  30.  
  31. 	return;
  32. }
  33. void shellsort2(char s[10001][14], int n) {
  34. 	unsigned int gaps[] = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929};
  35.  
  36. 	int i, j, k;
  37. 	int gap;
  38. 	char temp[14];
  39. 	for (k = 10; k >= 0; k --) {
  40. 		gap = gaps[k];
  41. 		for (i = gap; i < n; i++) {
  42. 			strcpy(temp,s[i]);
  43. 			for (j = i; j >= gap && strcmp(s[j-gap], temp) > 0; j -= gap)
  44. 				strcpy(s[j], s[j-gap]);
  45. 			strcpy(s[j], temp);
  46. 		}
  47. 	}
  48.  
  49. 	return;
  50. }
  51. int binsearch(char s[][10001][14], char x[], int low, int high) {
  52. 	int mid;
  53. 	while (low <= high) {
  54. 		mid = (low+high) / 2;
  55. 		if (strcmp(x, s[0][mid]) < 0)
  56. 			high = mid - 1;
  57. 		else if (strcmp(x, s[0][mid]) > 0)
  58. 			low = mid + 1;
  59. 		else 
  60. 			return mid;
  61. 	}
  62. }
  63. int binsearch2(char s[10001][14], char x[], int low, int high) {
  64. 	int mid;
  65. 	while (low <= high) {
  66. 		mid = (low+high) / 2;
  67. 		if (strcmp(x, s[mid]) < 0)
  68. 			high = mid - 1;
  69. 		else if (strcmp(x, s[mid]) > 0)
  70. 			low = mid + 1;
  71. 		else 
  72. 			return mid;
  73. 	}
  74. }
  75. char a[2][10001][14];
  76. char b[10001][14];
  77. int v1[10001], v2[10001];
  78. main()
  79. {
  80. 	int n, m;
  81. 	int c, i, j, k, l;
  82. 	char temp[14];
  83. 	int maxchef = 0, maxcountry = 0;
  84. 	char CHEF[14], COUNTRY[14];
  85. 	scan(&n);
  86. 	scan(&m);
  87. 	j = 0;
  88. 	while (n--) {
  89. 		i = 0;
  90. 		while ((c = getchar()) != ' ')
  91. 			a[0][j][i++] = c;
  92. 		a[0][j][i] = '\0';
  93. 		i = 0;
  94. 		while ((c = getchar()) != '\n')
  95. 			a[1][j][i++] = c;
  96. 		a[1][j][i] = '\0';
  97. 		strcpy(b[j], a[1][j]);
  98. 		j++;
  99. 	}
  100. 	shellsort(a, j);
  101. 	shellsort2(b, j);
  102. 	while (m--) {
  103. 		i = 0;
  104. 		while ((c = getchar()) != '\n' && c != EOF)
  105. 			temp[i++] = c;
  106. 		temp[i] = '\0';
  107. 		k = binsearch(a, temp, 0, j-1);
  108. 		v1[k]++;
  109. 		l = binsearch2(b, a[1][k], 0, j-1);
  110. 		v2[l]++;
  111. 	}
  112. 	maxchef = v1[0];
  113. 	strcpy(CHEF, a[0][0]);
  114. 	maxcountry = v2[0];
  115. 	strcpy(COUNTRY, b[0]);
  116. 	for (i = 1; i < j; i++) {
  117. 		if (maxchef == v1[i]) {
  118. 			if (strcmp(a[0][i], CHEF) < 0) {
  119. 				strcpy(CHEF, a[0][i]);
  120. 			}
  121. 		}
  122. 		else if (maxchef < v1[i]) {
  123. 			strcpy(CHEF, a[0][i]);
  124. 			maxchef = v1[i];
  125. 		}
  126. 		if (maxcountry == v2[i]) {
  127. 			if (strcmp(b[i], COUNTRY) < 0) {
  128. 				strcpy(COUNTRY, b[i]);
  129. 			}
  130. 		}
  131. 		else if (maxcountry < v2[i]) {
  132. 			strcpy(COUNTRY, b[i]);
  133. 			maxcountry = v2[i];
  134. 		}
  135. 	}
  136. 	printf("%s\n%s\n", COUNTRY, CHEF);
  137. 	return 0;
  138. }
Time limit exceeded #stdin #stdout 5s 2208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/q5vMIO
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!