fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4.  
  5. #define TEST_COUNT 1000
  6.  
  7.  
  8. typedef int bool;
  9. typedef int (*searcher)(int *A, int x, int l, int r);
  10.  
  11. int cmp(const void *a, const void *b) {
  12.     int i = *(int*)a;
  13. 	int j = *(int*)b;
  14. 	return (i < j) ? -1 : (i == j) ? 0 : 1;
  15. }
  16.  
  17. int linsearch(int *A, int x, int n) {
  18. 	int i;
  19. 	for (i = 0; i < n; i++) {
  20. 		if (A[i] == x) {
  21. 			return i;
  22. 		}
  23. 	}
  24. 	return -1;
  25. }
  26.  
  27. void print(int *A, int n) {
  28. 	printf("[");
  29. 	if (n > 0) {
  30. 		printf("%d", A[0]);
  31. 	}
  32. 	int i;
  33. 	for (i = 1; i < n; i++) {
  34. 		printf(", %d", A[i]);
  35. 	}
  36. 	printf("]\n");
  37. }
  38.  
  39. void test(searcher s) {
  40. 	if (s(0, 0, 0, 0) != -1) {
  41. 		printf("FAIL! []\n");
  42. 		return;
  43. 	}
  44.  
  45. 	int A[TEST_COUNT];
  46. 	int i, j;
  47. 	for (i = 1; i < TEST_COUNT; i++) {
  48. 		printf("(%d tests)...\r", i);
  49. 		fflush(stdout);
  50. 		for (j = 0; j < i; j++) {
  51. 			A[j] = abs(rand()) % i;
  52. 		}
  53. 		int x = abs(rand()) % i;
  54.  
  55. 		qsort(A, i, sizeof(int), cmp);
  56.  
  57. 		int k = s(A, x, 0, i);
  58. 		int l = linsearch(A,x,i);
  59. 		if (k == -1) {
  60. 			if (l != -1) {
  61. 				printf("\nFAIL! x = %d, k = %d, l = %d\n", x, k, l);
  62. 				print(A, i);
  63. 				return;
  64. 			}
  65. 		} else if (A[k] != x) {
  66. 			printf("\nFAIL! x = %d, k = %d, l = %d\n", x, k, l);
  67. 			print(A, i);
  68. 			return;
  69. 		}
  70. 	}
  71. 	printf("OK!                   \n");
  72. }
  73.  
  74.  
  75. int binSearch(int *xs, int x, int l, int r) {	
  76. 	if (l == r) { return -1; }	
  77. 	int m = (l+r-1)/2;
  78. 	return (xs[m] < x) ? binSearch(xs, x, m+1, r)
  79. 	     : (xs[m] > x) ? binSearch(xs, x, l, m)
  80. 	     :               m;
  81. }
  82.  
  83. int szuk_rek(int *A, int X, int L, int R){
  84. 	if (R < 0) return -1;
  85.  
  86. //        printf("L =%d R = %d\n", L, R);
  87.         if(A[L] > X || A[R] < X){
  88.                 return 0;
  89.         }
  90.         if(A[R]==X){
  91.                 return R;
  92.         }
  93.         if(L > R){
  94.                 return -1;
  95.         }
  96.         if( L == R && A[L] != X){
  97.                 return -1;
  98.         }
  99.  
  100.         if (A[(L+R)/2]== X){
  101.                 return (L+R)/2;
  102.         }
  103.  
  104.         if( A[(L+R)/2] < X){
  105.                 return szuk_rek(A, X, (L + R)/2, R);
  106.         }
  107.         if( A[(L+R)/2] > X){
  108.                 return szuk_rek(A, X, L, (L + R)/2);
  109.         }
  110.        return -1;
  111. }
  112.  
  113. int asdf(int *A, int X, int L, int R) {
  114. 	return szuk_rek(A,X,L,R-1);
  115. }
  116.  
  117. int main(void) {
  118. 	srand(7);
  119.  
  120. 	test(binSearch);
  121. 	test(asdf);
  122.  
  123. 	return 0;
  124. }
  125.  
Time limit exceeded #stdin #stdout 5s 1964KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(1 tests)...
(2 tests)...
(3 tests)...
(4 tests)...
(5 tests)...
(6 tests)...
(7 tests)...
(8 tests)...
(9 tests)...
(10 tests)...
(11 tests)...
(12 tests)...
(13 tests)...
(14 tests)...
(15 tests)...
(16 tests)...
(17 tests)...
(18 tests)...
(19 tests)...
(20 tests)...
(21 tests)...
(22 tests)...
(23 tests)...
(24 tests)...
(25 tests)...
(26 tests)...
(27 tests)...
(28 tests)...
(29 tests)...
(30 tests)...
(31 tests)...
(32 tests)...
(33 tests)...
(34 tests)...
(35 tests)...
(36 tests)...
(37 tests)...
(38 tests)...
(39 tests)...
(40 tests)...
(41 tests)...
(42 tests)...
(43 tests)...
(44 tests)...
(45 tests)...
(46 tests)...
(47 tests)...
(48 tests)...
(49 tests)...
(50 tests)...
(51 tests)...
(52 tests)...
(53 tests)...
(54 tests)...
(55 tests)...
(56 tests)...
(57 tests)...
(58 tests)...
(59 tests)...
(60 tests)...
(61 tests)...
(62 tests)...
(63 tests)...
(64 tests)...
(65 tests)...
(66 tests)...
(67 tests)...
(68 tests)...
(69 tests)...
(70 tests)...
(71 tests)...
(72 tests)...
(73 tests)...
(74 tests)...
(75 tests)...
(76 tests)...
(77 tests)...
(78 tests)...
(79 tests)...
(80 tests)...
(81 tests)...
(82 tests)...
(83 tests)...
(84 tests)...
(85 tests)...
(86 tests)...
(87 tests)...
(88 tests)...
(89 tests)...
(90 tests)...
(91 tests)...
(92 tests)...
(93 tests)...
(94 tests)...
(95 tests)...
(96 tests)...
(97 tests)...
(98 tests)...
(99 tests)...
(100 tests)...
(101 tests)...
(102 tests)...
(103 tests)...
(104 tests)...
(105 tests)...
(106 tests)...
(107 tests)...
(108 tests)...
(109 tests)...
(110 tests)...
(111 tests)...
(112 tests)...
(113 tests)...
(114 tests)...
(115 tests)...
(116 tests)...
(117 tests)...
(118 tests)...
(119 tests)...
(120 tests)...
(121 tests)...
(122 tests)...
(123 tests)...
(124 tests)...
(125 tests)...
(126 tests)...
(127 tests)...
(128 tests)...
(129 tests)...
(130 tests)...
(131 tests)...
(132 tests)...
(133 tests)...
(134 tests)...
(135 tests)...
(136 tests)...
(137 tests)...
(138 tests)...
(139 tests)...
(140 tests)...
(141 tests)...
(142 tests)...
(143 tests)...
(144 tests)...
(145 tests)...
(146 tests)...
(147 tests)...
(148 tests)...
(149 tests)...
(150 tests)...
(151 tests)...
(152 tests)...
(153 tests)...
(154 tests)...
(155 tests)...
(156 tests)...
(157 tests)...
(158 tests)...
(159 tests)...
(160 tests)...
(161 tests)...
(162 tests)...
(163 tests)...
(164 tests)...
(165 tests)...
(166 tests)...
(167 tests)...
(168 tests)...
(169 tests)...
(170 tests)...
(171 tests)...
(172 tests)...
(173 tests)...
(174 tests)...
(175 tests)...
(176 tests)...
(177 tests)...
(178 tests)...
(179 tests)...
(180 tests)...
(181 tests)...
(182 tests)...
(183 tests)...
(184 tests)...
(185 tests)...
(186 tests)...
(187 tests)...
(188 tests)...
(189 tests)...
(190 tests)...
(191 tests)...
(192 tests)...
(193 tests)...
(194 tests)...
(195 tests)...
(196 tests)...
(197 tests)...
(198 tests)...
(199 tests)...
(200 tests)...
(201 tests)...
(202 tests)...
(203 tests)...
(204 tests)...
(205 tests)...
(206 tests)...
(207 tests)...
(208 tests)...
(209 tests)...
(210 tests)...
(211 tests)...
(212 tests)...
(213 tests)...
(214 tests)...
(215 tests)...
(216 tests)...
(217 tests)...
(218 tests)...
(219 tests)...
(220 tests)...
(221 tests)...
(222 tests)...
(223 tests)...
(224 tests)...
(225 tests)...
(226 tests)...
(227 tests)...
(228 tests)...
(229 tests)...
(230 tests)...
(231 tests)...
(232 tests)...
(233 tests)...
(234 tests)...
(235 tests)...
(236 tests)...
(237 tests)...
(238 tests)...
(239 tests)...
(240 tests)...
(241 tests)...
(242 tests)...
(243 tests)...
(244 tests)...
(245 tests)...
(246 tests)...
(247 tests)...
(248 tests)...
(249 tests)...
(250 tests)...
(251 tests)...
(252 tests)...
(253 tests)...
(254 tests)...
(255 tests)...
(256 tests)...
(257 tests)...
(258 tests)...
(259 tests)...
(260 tests)...
(261 tests)...
(262 tests)...
(263 tests)...
(264 tests)...
(265 tests)...
(266 tests)...
(267 tests)...
(268 tests)...
(269 tests)...
(270 tests)...
(271 tests)...
(272 tests)...
(273 tests)...
(274 tests)...
(275 tests)...
(276 tests)...
(277 tests)...
(278 tests)...
(279 tests)...
(280 tests)...
(281 tests)...
(282 tests)...
(283 tests)...
(284 tests)...
(285 tests)...
(286 tests)...
(287 tests)...
(288 tests)...
(289 tests)...
(290 tests)...
(291 tests)...
(292 tests)...
(293 tests)...
(294 tests)...
(295 tests)...
(296 tests)...
(297 tests)...
(298 tests)...
(299 tests)...
(300 tests)...
(301 tests)...
(302 tests)...
(303 tests)...
(304 tests)...
(305 tests)...
(306 tests)...
(307 tests)...
(308 tests)...
(309 tests)...
(310 tests)...
(311 tests)...
(312 tests)...
(313 tests)...
(314 tests)...
(315 tests)...
(316 tests)...
(317 tests)...
(318 tests)...
(319 tests)...
(320 tests)...
(321 tests)...
(322 tests)...
(323 tests)...
(324 tests)...
(325 tests)...
(326 tests)...
(327 tests)...
(328 tests)...
(329 tests)...
(330 tests)...
(331 tests)...
(332 tests)...
(333 tests)...
(334 tests)...
(335 tests)...
(336 tests)...
(337 tests)...
(338 tests)...
(339 tests)...
(340 tests)...
(341 tests)...
(342 tests)...
(343 tests)...
(344 tests)...
(345 tests)...
(346 tests)...
(347 tests)...
(348 tests)...
(349 tests)...
(350 tests)...
(351 tests)...
(352 tests)...
(353 tests)...
(354 tests)...
(355 tests)...
(356 tests)...
(357 tests)...
(358 tests)...
(359 tests)...
(360 tests)...
(361 tests)...
(362 tests)...
(363 tests)...
(364 tests)...
(365 tests)...
(366 tests)...
(367 tests)...
(368 tests)...
(369 tests)...
(370 tests)...
(371 tests)...
(372 tests)...
(373 tests)...
(374 tests)...
(375 tests)...
(376 tests)...
(377 tests)...
(378 tests)...
(379 tests)...
(380 tests)...
(381 tests)...
(382 tests)...
(383 tests)...
(384 tests)...
(385 tests)...
(386 tests)...
(387 tests)...
(388 tests)...
(389 tests)...
(390 tests)...
(391 tests)...
(392 tests)...
(393 tests)...
(394 tests)...
(395 tests)...
(396 tests)...
(397 tests)...
(398 tests)...
(399 tests)...
(400 tests)...
(401 tests)...
(402 tests)...
(403 tests)...
(404 tests)...
(405 tests)...
(406 tests)...
(407 tests)...
(408 tests)...
(409 tests)...
(410 tests)...
(411 tests)...
(412 tests)...
(413 tests)...
(414 tests)...
(415 tests)...
(416 tests)...
(417 tests)...
(418 tests)...
(419 tests)...
(420 tests)...
(421 tests)...
(422 tests)...
(423 tests)...
(424 tests)...
(425 tests)...
(426 tests)...
(427 tests)...
(428 tests)...
(429 tests)...
(430 tests)...
(431 tests)...
(432 tests)...
(433 tests)...
(434 tests)...
(435 tests)...
(436 tests)...
(437 tests)...
(438 tests)...
(439 tests)...
(440 tests)...
(441 tests)...
(442 tests)...
(443 tests)...
(444 tests)...
(445 tests)...
(446 tests)...
(447 tests)...
(448 tests)...
(449 tests)...
(450 tests)...
(451 tests)...
(452 tests)...
(453 tests)...
(454 tests)...
(455 tests)...
(456 tests)...
(457 tests)...
(458 tests)...
(459 tests)...
(460 tests)...
(461 tests)...
(462 tests)...
(463 tests)...
(464 tests)...
(465 tests)...
(466 tests)...
(467 tests)...
(468 tests)...
(469 tests)...
(470 tests)...
(471 tests)...
(472 tests)...
(473 tests)...
(474 tests)...
(475 tests)...
(476 tests)...
(477 tests)...
(478 tests)...
(479 tests)...
(480 tests)...
(481 tests)...
(482 tests)...
(483 tests)...
(484 tests)...
(485 tests)...
(486 tests)...
(487 tests)...
(488 tests)...
(489 tests)...
(490 tests)...
(491 tests)...
(492 tests)...
(493 tests)...
(494 tests)...
(495 tests)...
(496 tests)...
(497 tests)...
(498 tests)...
(499 tests)...
(500 tests)...
(501 tests)...
(502 tests)...
(503 tests)...
(504 tests)...
(505 tests)...
(506 tests)...
(507 tests)...
(508 tests)...
(509 tests)...
(510 tests)...
(511 tests)...
(512 tests)...
(513 tests)...
(514 tests)...
(515 tests)...
(516 tests)...
(517 tests)...
(518 tests)...
(519 tests)...
(520 tests)...
(521 tests)...
(522 tests)...
(523 tests)...
(524 tests)...
(525 tests)...
(526 tests)...
(527 tests)...
(528 tests)...
(529 tests)...
(530 tests)...
(531 tests)...
(532 tests)...
(533 tests)...
(534 tests)...
(535 tests)...
(536 tests)...
(537 tests)...
(538 tests)...
(539 tests)...
(540 tests)...
(541 tests)...
(542 tests)...
(543 tests)...
(544 tests)...
(545 tests)...
(546 tests)...
(547 tests)...
(548 tests)...
(549 tests)...
(550 tests)...
(551 tests)...
(552 tests)...
(553 tests)...
(554 tests)...
(555 tests)...
(556 tests)...
(557 tests)...
(558 tests)...
(559 tests)...
(560 tests)...
(561 tests)...
(562 tests)...
(563 tests)...
(564 tests)...
(565 tests)...
(566 tests)...
(567 tests)...
(568 tests)...
(569 tests)...
(570 tests)...
(571 tests)...
(572 tests)...
(573 tests)...
(574 tests)...
(575 tests)...
(576 tests)...
(577 tests)...
(578 tests)...
(579 tests)...
(580 tests)...
(581 tests)...
(582 tests)...
(583 tests)...
(584 tests)...
(585 tests)...
(586 tests)...
(587 tests)...
(588 tests)...
(589 tests)...
(590 tests)...
(591 tests)...
(592 tests)...
(593 tests)...
(594 tests)...
(595 tests)...
(596 tests)...
(597 tests)...
(598 tests)...
(599 tests)...
(600 tests)...
(601 tests)...
(602 tests)...
(603 tests)...
(604 tests)...
(605 tests)...
(606 tests)...
(607 tests)...
(608 tests)...
(609 tests)...
(610 tests)...
(611 tests)...
(612 tests)...
(613 tests)...
(614 tests)...
(615 tests)...
(616 tests)...
(617 tests)...
(618 tests)...
(619 tests)...
(620 tests)...
(621 tests)...
(622 tests)...
(623 tests)...
(624 tests)...
(625 tests)...
(626 tests)...
(627 tests)...
(628 tests)...
(629 tests)...
(630 tests)...
(631 tests)...
(632 tests)...
(633 tests)...
(634 tests)...
(635 tests)...
(636 tests)...
(637 tests)...
(638 tests)...
(639 tests)...
(640 tests)...
(641 tests)...
(642 tests)...
(643 tests)...
(644 tests)...
(645 tests)...
(646 tests)...
(647 tests)...
(648 tests)...
(649 tests)...
(650 tests)...
(651 tests)...
(652 tests)...
(653 tests)...
(654 tests)...
(655 tests)...
(656 tests)...
(657 tests)...
(658 tests)...
(659 tests)...
(660 tests)...
(661 tests)...
(662 tests)...
(663 tests)...
(664 tests)...
(665 tests)...
(666 tests)...
(667 tests)...
(668 tests)...
(669 tests)...
(670 tests)...
(671 tests)...
(672 tests)...
(673 tests)...
(674 tests)...
(675 tests)...
(676 tests)...
(677 tests)...
(678 tests)...
(679 tests)...
(680 tests)...
(681 tests)...
(682 tests)...
(683 tests)...
(684 tests)...
(685 tests)...
(686 tests)...
(687 tests)...
(688 tests)...
(689 tests)...
(690 tests)...
(691 tests)...
(692 tests)...
(693 tests)...
(694 tests)...
(695 tests)...
(696 tests)...
(697 tests)...
(698 tests)...
(699 tests)...
(700 tests)...
(701 tests)...
(702 tests)...
(703 tests)...
(704 tests)...
(705 tests)...
(706 tests)...
(707 tests)...
(708 tests)...
(709 tests)...
(710 tests)...
(711 tests)...
(712 tests)...
(713 tests)...
(714 tests)...
(715 tests)...
(716 tests)...
(717 tests)...
(718 tests)...
(719 tests)...
(720 tests)...
(721 tests)...
(722 tests)...
(723 tests)...
(724 tests)...
(725 tests)...
(726 tests)...
(727 tests)...
(728 tests)...
(729 tests)...
(730 tests)...
(731 tests)...
(732 tests)...
(733 tests)...
(734 tests)...
(735 tests)...
(736 tests)...
(737 tests)...
(738 tests)...
(739 tests)...
(740 tests)...
(741 tests)...
(742 tests)...
(743 tests)...
(744 tests)...
(745 tests)...
(746 tests)...
(747 tests)...
(748 tests)...
(749 tests)...
(750 tests)...
(751 tests)...
(752 tests)...
(753 tests)...
(754 tests)...
(755 tests)...
(756 tests)...
(757 tests)...
(758 tests)...
(759 tests)...
(760 tests)...
(761 tests)...
(762 tests)...
(763 tests)...
(764 tests)...
(765 tests)...
(766 tests)...
(767 tests)...
(768 tests)...
(769 tests)...
(770 tests)...
(771 tests)...
(772 tests)...
(773 tests)...
(774 tests)...
(775 tests)...
(776 tests)...
(777 tests)...
(778 tests)...
(779 tests)...
(780 tests)...
(781 tests)...
(782 tests)...
(783 tests)...
(784 tests)...
(785 tests)...
(786 tests)...
(787 tests)...
(788 tests)...
(789 tests)...
(790 tests)...
(791 tests)...
(792 tests)...
(793 tests)...
(794 tests)...
(795 tests)...
(796 tests)...
(797 tests)...
(798 tests)...
(799 tests)...
(800 tests)...
(801 tests)...
(802 tests)...
(803 tests)...
(804 tests)...
(805 tests)...
(806 tests)...
(807 tests)...
(808 tests)...
(809 tests)...
(810 tests)...
(811 tests)...
(812 tests)...
(813 tests)...
(814 tests)...
(815 tests)...
(816 tests)...
(817 tests)...
(818 tests)...
(819 tests)...
(820 tests)...
(821 tests)...
(822 tests)...
(823 tests)...
(824 tests)...
(825 tests)...
(826 tests)...
(827 tests)...
(828 tests)...
(829 tests)...
(830 tests)...
(831 tests)...
(832 tests)...
(833 tests)...
(834 tests)...
(835 tests)...
(836 tests)...
(837 tests)...
(838 tests)...
(839 tests)...
(840 tests)...
(841 tests)...
(842 tests)...
(843 tests)...
(844 tests)...
(845 tests)...
(846 tests)...
(847 tests)...
(848 tests)...
(849 tests)...
(850 tests)...
(851 tests)...
(852 tests)...
(853 tests)...
(854 tests)...
(855 tests)...
(856 tests)...
(857 tests)...
(858 tests)...
(859 tests)...
(860 tests)...
(861 tests)...
(862 tests)...
(863 tests)...
(864 tests)...
(865 tests)...
(866 tests)...
(867 tests)...
(868 tests)...
(869 tests)...
(870 tests)...
(871 tests)...
(872 tests)...
(873 tests)...
(874 tests)...
(875 tests)...
(876 tests)...
(877 tests)...
(878 tests)...
(879 tests)...
(880 tests)...
(881 tests)...
(882 tests)...
(883 tests)...
(884 tests)...
(885 tests)...
(886 tests)...
(887 tests)...
(888 tests)...
(889 tests)...
(890 tests)...
(891 tests)...
(892 tests)...
(893 tests)...
(894 tests)...
(895 tests)...
(896 tests)...
(897 tests)...
(898 tests)...
(899 tests)...
(900 tests)...
(901 tests)...
(902 tests)...
(903 tests)...
(904 tests)...
(905 tests)...
(906 tests)...
(907 tests)...
(908 tests)...
(909 tests)...
(910 tests)...
(911 tests)...
(912 tests)...
(913 tests)...
(914 tests)...
(915 tests)...
(916 tests)...
(917 tests)...
(918 tests)...
(919 tests)...
(920 tests)...
(921 tests)...
(922 tests)...
(923 tests)...
(924 tests)...
(925 tests)...
(926 tests)...
(927 tests)...
(928 tests)...
(929 tests)...
(930 tests)...
(931 tests)...
(932 tests)...
(933 tests)...
(934 tests)...
(935 tests)...
(936 tests)...
(937 tests)...
(938 tests)...
(939 tests)...
(940 tests)...
(941 tests)...
(942 tests)...
(943 tests)...
(944 tests)...
(945 tests)...
(946 tests)...
(947 tests)...
(948 tests)...
(949 tests)...
(950 tests)...
(951 tests)...
(952 tests)...
(953 tests)...
(954 tests)...
(955 tests)...
(956 tests)...
(957 tests)...
(958 tests)...
(959 tests)...
(960 tests)...
(961 tests)...
(962 tests)...
(963 tests)...
(964 tests)...
(965 tests)...
(966 tests)...
(967 tests)...
(968 tests)...
(969 tests)...
(970 tests)...
(971 tests)...
(972 tests)...
(973 tests)...
(974 tests)...
(975 tests)...
(976 tests)...
(977 tests)...
(978 tests)...
(979 tests)...
(980 tests)...
(981 tests)...
(982 tests)...
(983 tests)...
(984 tests)...
(985 tests)...
(986 tests)...
(987 tests)...
(988 tests)...
(989 tests)...
(990 tests)...
(991 tests)...
(992 tests)...
(993 tests)...
(994 tests)...
(995 tests)...
(996 tests)...
(997 tests)...
(998 tests)...
(999 tests)...
OK!                   
(1 tests)...
(2 tests)...
(3 tests)...
(4 tests)...
https://ideone.com/upz4Ed
language:
C (gcc 8.3)
created:
12 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!