+/EE360C

algorithms

git clone https://git.julia.blue/+/EE360C

Joseph RyanUse binary search to achieve n^2logn performance8f725db

master
13.7 KiB2 linesraw
118237 25972 21093 12925 17569 6075 10653 9230 4019 23881 27452 10389 22460 10196 25684 15623 25873 17149 21103 11262 9973 12702 21580 26285 2518 10162 18620 18713 10820 28855 5543 18562 6564 10472 15027 11245 8644 21509 23410 15447 26891 7631 6496 22533 26751 20141 16688 19287 899 29724 11430 28213 29704 29080 13026 22951 14382 2335 11207 16822 23926 10882 2582 18704 7175 6051 29817 2375 845 14674 24872 17598 5161 20224 20253 141 24366 23620 18241 14855 17623 11434 3000 28479 1506 5732 6736 17466 494 7467 14149 58 3476 17220 15709 29106 21557 6360 122 19708 9327 7977 8845 15184 3305 20855 28778 18746 19091 9178 15031 15575 24556 23865 29722 26326 15457 2430 14982 19666 7567 12176 20874 23624 13493 10889 12079 9929 22272 3982 9015 5323 26769 15531 28294 25013 4498 19314 2572 6974 22193 6529 7406 3896 12090 12208 11476 18323 21193 29140 8630 13637 27072 9729 15104 1788 1653 7803 17131 28348 5619 26900 16724 2475 24203 11 15430 7643 8829 3157 25052 5962 13574 8802 17790 9756 28518 17555 4264 2419 21191 6287 27092 1398 13543 14005 26157 9817 27729 11071 8050 2724 20973 6647 16758 22142 14025 5654 18637 9124 23817 9033 21585 16205 28060 19264 13513 8331 15537 1271 16516 10512 1588 29716 1662 4789 18220 7651 6452 27322 23472 3860 13984 16995 4679 19620 24622 29224 9545 9198 19475 17529 1446 11308 1587 16978 4688 12258 13153 12797 8150 17957 5429 10137 942 8902 12381 29605 5218 11986 7446 18081 14280 12852 21772 18976 21915 10839 20987 22530 21048 7042 9059 9726 16927 559 10207 13672 19756 14061 921 22768 27329 14833 20599 22707 28620 13159 4811 20445 19084 16479 22696 5200 4527 5029 18816 2075 996 18896 4343 11889 6090 15428 10552 2238 29668 29948 21283 29674 29598 21591 18601 15548 11556 5742 11253 3441 9488 15679 17740 10525 14700 3013 20059 12029 10461 25732 28122 10381 21950 8953 7496 9458 19919 6910 25827 8967 14700 23074 15516 5822 22588 19814 23663 22504 9869 28638 21466 23473 29564 14754 20145 21305 21758 27637 22200 4230 21776 20824 13560 17312 8553 27186 34 28367 7329 13160 27989 26843 29681 24626 7659 5454 13309 8937 4952 28294 410 6461 10601 23739 25393 3675 7249 4659 17398 11521 21064 15760 11944 5690 27860 11791 19321 14695 26955 19234 14715 2135 22685 13622 18326 9517 8004 17493 27271 28387 20201 19443 14802 19140 14128 10592 22839 10162 13616 21531 28912 17826 28261 14594 17988 16110 16513 27495 5646 25574 6876 20818 3357 8506 28799 7911 3262 20386 4977 8405 21015 5109 2326 17955 26529 11533 24664 23279 14917 18160 16686 20556 18217 19262 23734 20302 10986 8502 4877 3519 7712 20797 20717 1632 19701 15130 656 27676 25749 15115 25581 25241 11093 5369 23400 12055 4480 20959 27600 15489 2816 28057 23020 4195 23317 24325 17420 26803 14144 21843 20394 27575 26362 20483 18108 24608 19457 25817 27504 29619 19517 12280 8620 2247 20178 8668 29993 26190 5735 7848 9158 28346 17027 20080 9627 27409 18642 18328 22907 29631 24472 20489 13397 17880 899 25535 11305 21913 24169 15301 12858 12967 24707 2504 15106 15206 11569 29541 26053 2503 4999 10817 29326 11731 13154 8492 17732 22579 15888 27830 13161 18365 4273 15681 18272 3702 23729 15336 11745 1399 27747 28738 21828 27850 15483 6349 19145 10063 9464 18189 1058 4634 22912 5838 18085 5687 9464 2632 853 17573 8453 25648 11323 26663 19487 12948 26140 12253 17409 28171 8700 16012 23836 22661 20586 16885 9497 22068 5224 22607 2626 8311 27320 11248 7520 20557 6494 17163 2401 1014 7695 12063 24594 9721 21339 9872 22569 28903 14247 20881 17572 467 12225 24572 16522 16754 28125 1075 2993 21579 14287 26924 9177 23646 4973 20379 18711 22626 5352 1528 17747 6867 15477 11677 1616 13365 12644 23392 12015 1401 28985 12909 7047 7232 12898 7868 29310 22992 29 22049 1986 28445 5358 12241 21517 6664 912 384 29041 21285 6687 9322 18133 3465 5545 4341 9208 22029 476 22332 22086 17465 23355 22983 2336 9881 29569 1028 6597 29116 15463 19876 12931 28852 14792 22178 9413 6650 23907 18550 5029 24702 14142 3603 29448 19087 21429 14838 27136 29534 9064 23250 8958 23741 26944 4323 22274 8076 24939 16256 12955 14252 9891 28188 22253 25035 9375 15960 15754 18881 25373 27445 6716 1681 10813 6452 4777 25681 17688 3021 29627 23645 23916 13269 16791 27512 795 20807 20021 28728 832 23491 24506 6033 2592 8779 20733 1989 4965 22528 16013 7916 24623 15902 26820 12197 9375 3661 3186 18828 25667 22895 5641 21033 17935 21335 14100 17192 11253 25261 15102 3447 22090 17124 9276 20891 17021 4666 6894 10624 6071 4329 15278 24237 12980 23057 1657 8162 14423 15973 3019 11358 13550 28586 16188 3459 8202 15092 6194 1663 2303 23017 24948 29342 28808 7107 18336 930 11748 19806 21164 17289 19973 7435 13619 11929 29200 10023 24449 7742 19353 8732 9 252 21293 20009 26244 12731 6925 27752 22965 4463 22270 25475 538 5499 68 13048 16858 2428 22615 19751 28266 29154 16025 7298 11616 24626 24795 28831 2391 476 15912 6481 27278 564 775 20244 29476 28722 7678 8883 17992 26336 23887 13227 25049 988 28420 19997 16984 10730 18375 17403 17750 26173 358 7751 22171 12783 4952 19069 17870 25709 27783 11678 21592 14969 21899 28805 22618 23317 20773 14045 6227 24686 11646 19633 25385 24781 7918 4837 8593 20821 9513 4244 27783 28181 18429 9475 3976 11785 27621 16173 20833 28463 28975 8913 22543 20079 13758 5667 24651 27516 27074 20273 12516 25710 20632 1202 29398 25816 22291 2595 28954 24198 135 10734 19855 17410 7680 10778 20727 28966 19484 8917 2082 5334 14591 1309 1135 9224 3510 4215 13247 7895 4629 14832 27128 18676 6318 22008 13448 23895 12185 2730 4488 21416 1874 24698 25202 28794 8968 18959 19375 8921 5587 9405 15097 26417 27146 15515 10143 15098 2469 27542 29957 27441 19354 28745 3914 19587 7841 15383 6320 16503 12832 21835 24546 2554 20685 9493 2263 20094 29338 26221 13935 15762 24240 3224 13819 6900 27181 11236 20518 1862 11205 16377 4832 1152 29080 3129 27581 4409 29723 216 22704 25831 20986 8969 929 11179 25924 13943 18793 11991 3221 4565 5338 204 14949 23217 27070 4275 23644 3232 28611 12296 2265 1527 24222 27493 25520 9023 19249 21776 28651 16946 1849 25566 10267 12620 8469 16870 10171 16262 18783 1062 7640 11811 18029 27372 15001 1986 19267 10497 21035 23673 17660 1169 13236 22776 18130 3655 14704 29092 29844 8157 25285 20452 1951 2208 28831 25408 6739 25702 6580 19284 22821 23067 17890 11692 25117 12197 23701 6710 21185 387 798 6058 18138 9172 3880 26150 19310 19757 20950 28321 16615 1514 23205 1637 2024 1401 16847 19975 14346 7689 21667 27997 1560 7583 19916 5297 17177 27983 5804 4489 13111 10170 992 27873 9647 361 28175 15918 27128 28119 17555 21664 15820 16854 20706 16493 14810 28130 22762 13342 4262 20699 9423 26784 725 8393 12022 28865 24293 259 24311 799 23187 19626 3584 23405 20425 26640 3717 6789 4433 13967 22831 2413 1157 5958 20588 17880 10560 28589 23402 22590 27479 9649 15199 24083 11457 28031 14631 23047 9991 21905 10785 26431 16053 25502 8459 15714 1599 18146 17681 25995 8158 20226 27751 3529 18647 14650 26390 25410 5789 615 18322 21196 20772 15327 16370 25544 3595 17096 11428 21942 27839 3030 3711 29523 10337 5316 7621 10314 14961 20074 14857 16228 14201 21862 4881 15324 17082 675 9805 20625 28345 11859 9442 4947 26103 27232 14326 16769 652 11774 21536 26078 13655 25762 24754 22664 28363 12415 5732 22432 2315 15542 760 20646 14862 17188 21819 2669 3244 8931 23778 15409 29813 8939 14238 20519 20813 19938 16640 10446 2541 13507 18523 27841 26106 25478 13700 8523 9016 9876 7644 22903 19009 3703 10954 25047 7530 8870 28473 8209 12925 6432 19639 10524 12142 25458 29124 20461 29665 29580 7074 12691 23654 17530 20648 25375 20064 4193 23720 3360 2014 8438 9757 26241 28715 7237 27909 13731 13449 27005 5197 22879 25448 28181 16043 3884 21320 28869 11796 598 5888 11064 25528 9074 4134 8367 18295 24822 8583 11855 1075 22390 57 18993 6902 5989 21034 14851 22251 29392 24887 8316 6409 13125 7386 19265 18937 28402 23675 13080 1772 11626 18239 4853 14000 28497 2247 10210 8837 5203 10544 7570 5178 15261 15920 8661 533 28871 22928 18648 26253 21244 25598 24940 13741 27581 22814 21029 3613 18516 26594 2672 19359 6430 10902 18366 5729 25277 5459 10952 784 317 16482 14845 3937 15655 26559 2065 13566 19911 21062 15053 14245 4953 19238 25288 29626 24777 11677 2474 39 3209 25337 4735 26596 21472 28567 4220 12242 268 20808 15781 12809 15538 25362 15526 3489 3098 3242 17111 27810 14945 12192 15477 8422 12662 5258 5145 23017 13443 10560 14422 26598 18435 21640 7786 9085 11451 24744 8993 14650 21082 22987 7503 6585 2072 14070 12793 20989 21867 22090 3909 20797 28820 22575 26307 15987 8349 25566 25883 13235 25392 19019 22119 13916 19922 25777 25792 29140 6972 7367 16414 19089 6166 26172 3017 11998 11225 512 29216 27917 1621 13805 12178 18247 789 21503 25244 7901 8554 9127 19697 1618 5187 20423 15604 7854 13352 9396 14235 9087 28175 11412 8533 20438 19837 9749 7328 15780 21832 17278 19274 2856 20013 21050 4314 11137 28779 11640 22935 22752 450 13001 553 22648 27099 25011 7420 14820 2808 18171 7794 28835 26881 14526 23744 8244 9774 26607 27764 7633 25918 3681 13728 2459 17885 21329 14443 16506 22995 1422 5841 24030 17837 12280 14212 6380 14433 14073 702 15017 20874 23196 23441 13137 28541 27421 6624 5848 11929 17021 26926 18376 9476 9316 16480 5897 2341 22065 27334 9460 24704 10923 6648 21690 15084 14341 28754 7250 16865 17961 16667 1514 18432 23236 24347 18137 22081 5263 16299 14531 12083 4318 9630 23454 6480 5739 5998 14344 19742 27048 13718 26017 14226 15973 28564 8364 24498 1082 10835 9598 3130 9526 16973 13635 5184 28817 8176 2787 11635 5086 24672 3804 14370 15513 8787 13750 15459 16648 5141 28747 11557 7667 7416 15288 28782 4476 21869 5135 13287 8668 16696 9355 3972 24925 24287 7530 15513 29592 15957 6826 5051 1489 4965 22269 20222 17741 6077 27473 19026 1102 4125 14476 26631 3467 28478 4275 25658 27129 7433 24524 13730 5909 23637 1091 81 197 13620 720 7102 18103 8819 27205 10849 4019 6642 14198 1996 14252 13131 21686 12205 9435 22819 2133 25927 15923 9344 13522 19731 10997 15158 15396 27593 3647 848 3240 25231 23733 20171 13034 12129 7576 23956 29187 23695 3205 10668 5641 23821 24852 4030 8361 10132 11920 27336 18777 453 26189 7355 15016 10730 25137 765 4875 28401 28020 24384 26278 7365 23354 1282 7216 28860 7889 28611 14254 24883 15729 19336 21148 14370 6271 9075 24717 6299 12544 18570 538 16367 18104 24622 17423 13398 11735 28138 10458 26270 217 14460 19315 25152 8904 8109 4375 1340 24802 25751 3419 1631 10619 27093 22285 16994 18366 22284 12026 16852 3037 4101 20475 16320 10293 4898 1932 3074 15013 2517 25256 18600 25193 9147 25229 8552 27827 2765 26471 14126 12285 4400 5761 20931 12098 15310 24568 27060 5173 6751 26766 8389 10468 5472 13741 21735 20197 1895 6082 6150 27503 23400 19564 17365 95 15622 23546 29426 13105 559 14975 4848 22726 26709 27393 10034 24528 29067 23590 26509 10069 6631 21326 26672 25266 15144 866 25129 5191 29996 8718 25224 2867 1264 14336 12401 7535 24780 29764 28188 254 21603 5762 13352 10237 16874 7595 7735 21363 7298 27338 17828 28256 22669 21067 16991 16795 4931 1106 28069 16386 10593 12592 25354 10853 5183 6514 26431 10352 6472 26138 27616 28683 29134 14856 8871 24344 14630 14757 23819 4007 8019 24369 19871 26342 15686 21236 3979 22726 5141 1572 11308 6945 6609 23739 11531 12273 24560 28034 10959 24295 9439 18733 21523 14171 13692 27555 23232 2250 6629 21565 8547 16278 14246 21131 6963 19159 5890 9367 27619 5056 25369 4857 28662 29010 11219 11639 27820 15427 15862 14063 21137 9788 6186 23239 23959 28742 29835 17784 12739 2219 24984 6066 15975 3889 28186 18400 13206 7580 23543 9930 15183 2700 12191 20659 792 16873 3754 16622 6812 28313 14558 4570 2733 22963 3966 16433 9666 24954 1759 26604 22079 932 14060 8487 22804 12967 15327 15592 22083 4093 6541 29903 8597 27991 15638 3915 22583 23388 14521 5555 4028 15147 13871 5280 23868 2643 26087 5822 16899 24967 26735 18128 13688 11875 23061 7980 26545 16748 17223 22583 12770 4591 20148 22291 10566 14002 29651 8506 19850 14744 18688 20178 20270 6445 28784 7727 2516 20984 24450 404 6837 7159 25174 29975 3192 17232 23142 8494 9344 1073 28460 18264 22493 4838 25553 20184 7531 28756 23340 25968 1115 14858 18563 4761 4962 1331 319 1235 29744 10483 10890 726 13161 145 4826 9988 13960 10936 314 17839 18139 13551 18484 19701 7049 10711 7790 23195 21255 4012 22235 25231 2740 4204 10745 2785 9124 22010 27868 20934 9798 9078 4215 15749 18409 26519 5016 18138 29348 8855 3866 14052 4291 13694 7776 5915 2881 201 17676 25733 10707 20091 24373 25362 20882 28099 17346 15075 12145 15771 24321 13923 14846 4399 11829 6178 11422 21795 13990 9380 2232 10054 21520 14845 27513 16049 20436 10 26138 4196 8793 11375 19719 12545 14894 23021 16591 5054 24102 5999 3220 15876 16718 22371 12621 23489 352 9071 11819 26020 5300 22624 21222 28459 10803 17089 2594 3472 22817 24700 27727 1214 4678 16475 17723 28224 3992 1585 5387 22561 19710 14561 29927 22312 2792 22285 11080 4298 904 14426 7986 2156 4041 18322 18282 353 13922 2535 12042 13110 29252 10511 17228 23761 22572 22103 5188 11787 5086 574 3422 21906 23809 23330 13622 7332 7416 21126 21465 23193 28874 12857 1249 5085 17665 5169 5195 29236 21661 23415 27119 5207 16850 460 858 12373 13604 4917 3457 26314 3468 18831 35 13288 15876 16901 7852 25041 14071 22869 17199 26798 7536 18652 24370 18451 24524 25846 18900 15306 14846 20972 10002 14222 5754 22300 1605 14723 23625 24990 3596 13915 11003 8347 12688 4677 1536 21850 523 333 13089 15860 18400 25702 2620 15912 26994 25860 8910 13947 27970 12662 28160 606 3884 20429 18951 17626 28421 17569 26540 20636 1694 10837 27979 2243 13799 1781 13780 5634 24497 6832 18679 1368 15828 8472 6441 7544 379 14819 5657 27712 25915 28502 27980 14527 20414 1149 10718 18521 23062 15243 17192 28131 13706 7247 4932 17208 10937 23446 16899 2138 8747 27186 18617 12919 18377 19897 11687 14173 7316 4944 3713 27453 11998 17131 14695 24932 17788 25114 28727 21759 4029 9556 16905 13772 21867 20788 12832 12631 18486 17058 4900 8356 15008 28203 15651 14405 21939 12041 14910 19197 8186 13238 8279 24220 2007 13830 25907 32 27056 14964 23233 10217 39 7892 22497 21089 1210 2723 21186 5861 28993 8334 10130 15541 2820 5121 3100 29165 3513 20730 12340 13841 29090 26984 26347 1700 15313 13613 4175 5297 2180 
237412539