fork download
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <climits>
  4. #include <sstream>
  5. #include <algorithm>
  6. #include <cstring>
  7. #include <limits>
  8. #include <ctime>
  9.  
  10. using namespace std;
  11.  
  12. struct progress_timer {
  13. clock_t c;
  14. progress_timer() : c(clock()) { }
  15. int elapsed() {
  16. return clock() - c;
  17. }
  18. ~progress_timer() {
  19. clock_t d = clock() - c;
  20. cout << d / CLOCKS_PER_SEC << "."
  21. << (((d * 1000) / CLOCKS_PER_SEC) % 1000 / 100)
  22. << (((d * 1000) / CLOCKS_PER_SEC) % 100 / 10)
  23. << (((d * 1000) / CLOCKS_PER_SEC) % 10)
  24. << " s" << endl;
  25. }
  26. };
  27.  
  28. namespace user_voigt_timo {
  29. const char digit_pairs[201] = {
  30. "00010203040506070809"
  31. "10111213141516171819"
  32. "20212223242526272829"
  33. "30313233343536373839"
  34. "40414243444546474849"
  35. "50515253545556575859"
  36. "60616263646566676869"
  37. "70717273747576777879"
  38. "80818283848586878889"
  39. "90919293949596979899"
  40. };
  41.  
  42.  
  43. std::string& itostr(int n, std::string& s)
  44. {
  45. if(n==0)
  46. {
  47. s="0";
  48. return s;
  49. }
  50.  
  51. int sign = -(n<0);
  52. unsigned int val = (n^sign)-sign;
  53.  
  54. int size;
  55. if(val>=10000)
  56. {
  57. if(val>=10000000)
  58. {
  59. if(val>=1000000000)
  60. size=10;
  61. else if(val>=100000000)
  62. size=9;
  63. else
  64. size=8;
  65. }
  66. else
  67. {
  68. if(val>=1000000)
  69. size=7;
  70. else if(val>=100000)
  71. size=6;
  72. else
  73. size=5;
  74. }
  75. }
  76. else
  77. {
  78. if(val>=100)
  79. {
  80. if(val>=1000)
  81. size=4;
  82. else
  83. size=3;
  84. }
  85. else
  86. {
  87. if(val>=10)
  88. size=2;
  89. else
  90. size=1;
  91. }
  92. }
  93. size -= sign;
  94. s.resize(size);
  95. char* c = &s[0];
  96. if(sign)
  97. *c='-';
  98.  
  99. c += size-1;
  100. while(val>=100)
  101. {
  102. int pos = val % 100;
  103. val /= 100;
  104. memcpy(c-1, digit_pairs+2*pos, 2);
  105. c-=2;
  106. }
  107. while(val>0)
  108. {
  109. *c--='0' + (val % 10);
  110. val /= 10;
  111. }
  112. return s;
  113. }
  114.  
  115. std::string& itostr(unsigned val, std::string& s)
  116. {
  117. if(val==0)
  118. {
  119. s="0";
  120. return s;
  121. }
  122.  
  123. int size;
  124. if(val>=10000)
  125. {
  126. if(val>=10000000)
  127. {
  128. if(val>=1000000000)
  129. size=10;
  130. else if(val>=100000000)
  131. size=9;
  132. else
  133. size=8;
  134. }
  135. else
  136. {
  137. if(val>=1000000)
  138. size=7;
  139. else if(val>=100000)
  140. size=6;
  141. else
  142. size=5;
  143. }
  144. }
  145. else
  146. {
  147. if(val>=100)
  148. {
  149. if(val>=1000)
  150. size=4;
  151. else
  152. size=3;
  153. }
  154. else
  155. {
  156. if(val>=10)
  157. size=2;
  158. else
  159. size=1;
  160. }
  161. }
  162.  
  163. s.resize(size);
  164. char* c = &s[size-1];
  165. while(val>=100)
  166. {
  167. int pos = val % 100;
  168. val /= 100;
  169. memcpy(c-1, digit_pairs+2*pos, 2);
  170. c-=2;
  171. }
  172. while(val>0)
  173. {
  174. *c--='0' + (val % 10);
  175. val /= 10;
  176. }
  177. return s;
  178. }
  179.  
  180.  
  181. template <typename T>
  182. std::string itostr(T t) {
  183. std::string ret;
  184. itostr(t, ret);
  185. return ret;
  186. }
  187. }
  188.  
  189. namespace hopman_fun {
  190.  
  191. template <typename T>
  192. T reduce2(T v) {
  193. T k = ((v * 410) >> 12) & 0x000F000F000F000Full;
  194. return (((v - k * 10) << 8) + k);
  195. }
  196.  
  197. template <typename T>
  198. T reduce4(T v) {
  199. T k = ((v * 10486) >> 20) & 0xFF000000FFull;
  200. return reduce2(((v - k * 100) << 16) + (k));
  201. }
  202.  
  203. typedef unsigned long long ull;
  204. inline ull reduce8(ull v) {
  205. ull k = ((v * 3518437209u) >> 45);
  206. return reduce4(((v - k * 10000) << 32) + (k));
  207. }
  208.  
  209. template <typename T>
  210. std::string itostr(T o) {
  211. union {
  212. char str[16];
  213. unsigned short u2[8];
  214. unsigned u4[4];
  215. unsigned long long u8[2];
  216. };
  217.  
  218. unsigned v = o < 0 ? ~o + 1 : o;
  219.  
  220. u8[0] = (ull(v) * 3518437209u) >> 45;
  221. u8[0] = (u8[0] * 28147497672ull);
  222. u8[1] = v - u2[3] * 100000000;
  223.  
  224. u8[1] = reduce8(u8[1]);
  225. char* f;
  226. if (u2[3]) {
  227. u2[3] = reduce2(u2[3]);
  228. f = str + 6;
  229. } else {
  230. unsigned short* k = u4[2] ? u2 + 4 : u2 + 6;
  231. f = *k ? (char*)k : (char*)(k + 1);
  232. }
  233. if (!*f) f++;
  234.  
  235. u4[1] |= 0x30303030;
  236. u4[2] |= 0x30303030;
  237. u4[3] |= 0x30303030;
  238. if (o < 0) *--f = '-';
  239. return std::string(f, (str + 16) - f);
  240. }
  241. }
  242.  
  243.  
  244.  
  245. namespace hopman_fast {
  246.  
  247.  
  248. struct itostr_helper {
  249. static unsigned out[10000];
  250.  
  251. itostr_helper() {
  252. progress_timer t;
  253. for (int i = 0; i < 10000; i++) {
  254. unsigned v = i;
  255. char * o = (char*)(out + i);
  256. o[3] = v % 10 + '0';
  257. o[2] = (v % 100) / 10 + '0';
  258. o[1] = (v % 1000) / 100 + '0';
  259. o[0] = (v % 10000) / 1000;
  260. if (o[0]) o[0] |= 0x30;
  261. else if (o[1] != '0') o[0] |= 0x20;
  262. else if (o[2] != '0') o[0] |= 0x10;
  263. else o[0] |= 0x00;
  264. }
  265. }
  266. };
  267. unsigned itostr_helper::out[10000];
  268.  
  269. itostr_helper hlp_init;
  270.  
  271. template <typename T>
  272. std::string itostr(T o) {
  273. typedef itostr_helper hlp;
  274.  
  275. unsigned blocks[3], *b = blocks + 2;
  276. blocks[0] = o < 0 ? ~o + 1 : o;
  277. blocks[2] = blocks[0] % 10000; blocks[0] /= 10000;
  278. blocks[2] = hlp::out[blocks[2]];
  279.  
  280. if (blocks[0]) {
  281. blocks[1] = blocks[0] % 10000; blocks[0] /= 10000;
  282. blocks[1] = hlp::out[blocks[1]];
  283. blocks[2] |= 0x30303030;
  284. b--;
  285. }
  286.  
  287. if (blocks[0]) {
  288. blocks[0] = hlp::out[blocks[0] % 10000];
  289. blocks[1] |= 0x30303030;
  290. b--;
  291. }
  292.  
  293. char* f = ((char*)b);
  294. f += 3 - (*f >> 4);
  295.  
  296. char* str = (char*)blocks;
  297. if (o < 0) *--f = '-';
  298. return std::string(f, (str + 12) - f);
  299. }
  300. }
  301.  
  302. namespace voigt {
  303.  
  304.  
  305. template<typename T>
  306. struct assert_integral
  307. {
  308. enum { value = (T)0.5 };
  309. char test[1 - 4 * value];
  310. };
  311.  
  312. template<typename T, bool is_signed, size_t bits>
  313. struct itostr_impl { };
  314.  
  315. template<typename T, bool is_signed>
  316. struct itostr_impl<T,is_signed,8>
  317. {
  318. static std::string cvt(T val)
  319. {
  320. std::string retval(5, '\0');
  321. int i = 0;
  322. char ch = 0;
  323.  
  324. if (is_signed) {
  325. if (val < 0) {
  326. retval[i] = '-';
  327. ++i;
  328. if (val <= -100) {
  329. ch = '1';
  330. val += 100;
  331. }
  332. val = -val;
  333. }
  334. else if (val >= 100) {
  335. ch |= '1';
  336. val -= 100;
  337. }
  338. }
  339. else {
  340. if (val >= 200) {
  341. ch |= '2';
  342. val -= 200;
  343. }
  344. else if (val >= 100) {
  345. ch |= '1';
  346. val -= 100;
  347. }
  348. }
  349. if (ch) {
  350. retval[i] = ch;
  351. ++i;
  352. ch = '0';
  353. }
  354.  
  355. if (val >= 80) {
  356. ch |= '8';
  357. val -= 80;
  358. }
  359. else if (val >= 40) {
  360. ch |= '4';
  361. val -= 40;
  362. }
  363. if (val >= 20) {
  364. ch |= '2';
  365. val -= 20;
  366. }
  367. if (val >= 10) {
  368. ch |= '1';
  369. val -= 10;
  370. }
  371. if (ch) {
  372. retval[i] = ch;
  373. ++i;
  374. }
  375.  
  376. retval[i] = '0' + val;
  377. retval.resize(i+1);
  378.  
  379. return retval;
  380. }
  381. };
  382.  
  383. template<typename T, bool is_signed>
  384. struct itostr_impl<T,is_signed,16>
  385. {
  386. static std::string cvt(T val)
  387. {
  388. std::string retval(7, '\0');
  389. int i = 0;
  390. char ch = 0;
  391.  
  392. if (is_signed) {
  393. if (val < 0) {
  394. retval[i] = '-';
  395. ++i;
  396. if (val <= -20000) {
  397. ch = '2';
  398. val += 20000;
  399. }
  400. val = -val;
  401. }
  402. else if (val >= 20000) {
  403. ch |= '2';
  404. val -= 20000;
  405. }
  406. }
  407. else {
  408. if (val >= 40000) {
  409. ch |= '4';
  410. val -= 40000;
  411. }
  412. else if (val >= 20000) {
  413. ch |= '2';
  414. val -= 20000;
  415. }
  416. }
  417. if (val >= 10000) {
  418. ch |= '1';
  419. val -= 10000;
  420. }
  421.  
  422. if (ch) {
  423. retval[i] = ch;
  424. ++i;
  425. ch = '0';
  426. }
  427.  
  428. if (val >= 8000) {
  429. ch |= '8';
  430. val -= 8000;
  431. }
  432. else if (val >= 4000) {
  433. ch |= '4';
  434. val -= 4000;
  435. }
  436. if (val >= 2000) {
  437. ch |= '2';
  438. val -= 2000;
  439. }
  440. if (val >= 1000) {
  441. ch |= '1';
  442. val -= 1000;
  443. }
  444. if (ch) {
  445. retval[i] = ch;
  446. ++i;
  447. ch = '0';
  448. }
  449.  
  450. if (val >= 800) {
  451. ch |= '8';
  452. val -= 800;
  453. }
  454. else if (val >= 400) {
  455. ch |= '4';
  456. val -= 400;
  457. }
  458. if (val >= 200) {
  459. ch |= '2';
  460. val -= 200;
  461. }
  462. if (val >= 100) {
  463. ch |= '1';
  464. val -= 100;
  465. }
  466. if (ch) {
  467. retval[i] = ch;
  468. ++i;
  469. ch = '0';
  470. }
  471.  
  472. if (val >= 80) {
  473. ch |= '8';
  474. val -= 80;
  475. }
  476. else if (val >= 40) {
  477. ch |= '4';
  478. val -= 40;
  479. }
  480. if (val >= 20) {
  481. ch |= '2';
  482. val -= 20;
  483. }
  484. if (val >= 10) {
  485. ch |= '1';
  486. val -= 10;
  487. }
  488. if (ch) {
  489. retval[i] = ch;
  490. ++i;
  491. }
  492.  
  493. retval[i] = '0' + val;
  494. retval.resize(i+1);
  495.  
  496. return retval;
  497. }
  498. };
  499.  
  500.  
  501. const char digit_pair_table[201] = {
  502. "00010203040506070809"
  503. "10111213141516171819"
  504. "20212223242526272829"
  505. "30313233343536373839"
  506. "40414243444546474849"
  507. "50515253545556575859"
  508. "60616263646566676869"
  509. "70717273747576777879"
  510. "80818283848586878889"
  511. "90919293949596979899"
  512. };
  513.  
  514. template<typename T, bool is_signed>
  515. struct itostr_impl<T,is_signed,32>
  516. {
  517. static std::string cvt(T val)
  518. {
  519. char buf[11], ch = 0;
  520. char* start = buf + 1;
  521. char* p = start;
  522. bool neg = val < 0;
  523. int digit;
  524.  
  525. if (is_signed) {
  526. if (neg) {
  527. if (val <= -2000000000) {
  528. ch = '2';
  529. val += 2000000000;
  530. }
  531. val = -val;
  532. }
  533. else if (val >= 2000000000) {
  534. ch = '2';
  535. val -= 2000000000;
  536. }
  537. }
  538. else {
  539. if (val >= 4000000000U) {
  540. ch |= '4';
  541. val -= 4000000000U;
  542. }
  543. else if (val >= 2000000000) {
  544. ch |= '2';
  545. val -= 2000000000;
  546. }
  547. }
  548. if (val >= 1000000000) {
  549. ch |= '1';
  550. val -= 1000000000;
  551. }
  552.  
  553. if (ch) {
  554. *p = ch;
  555. ++p;
  556. ch = '0';
  557. }
  558. else if (val < 1000) {
  559. if (val < 10) goto d1;
  560. if (val < 1000) goto d10;
  561. }
  562. else {
  563. if (val < 100000) goto d1000;
  564. if (val < 10000000) goto d100000;
  565. }
  566.  
  567. #define DO_PAIR(n) \
  568.   d##n: \
  569.   digit = val / n; \
  570.   *(p++) = digit_pair_table[digit*2]; \
  571.   *(p++) = digit_pair_table[digit*2+1]; \
  572.   val -= n * digit;
  573.  
  574. DO_PAIR(10000000);
  575. DO_PAIR(100000);
  576. DO_PAIR(1000);
  577. DO_PAIR(10);
  578.  
  579. d1:
  580. *p = '0' | val;
  581.  
  582. if (p > start && *start == '0') ++start;
  583.  
  584. if (is_signed && neg) *--start = '-';
  585.  
  586. return std::string(start, p+1-start);
  587. }
  588. };
  589.  
  590. template<typename T>
  591. std::string itostr(T val)
  592. {
  593. sizeof(assert_integral<T>);
  594. return itostr_impl<T,((T)-1) < 0,sizeof(T) * CHAR_BIT>::cvt(val);
  595. }
  596.  
  597.  
  598. }
  599.  
  600. namespace ergosys {
  601.  
  602. typedef unsigned buf_t;
  603.  
  604. static buf_t * reduce(unsigned val, buf_t * stp) {
  605. unsigned above = val / 10000;
  606. if (above != 0) {
  607. stp = reduce(above, stp);
  608. val -= above * 10000;
  609. }
  610.  
  611. buf_t digit = val / 1000;
  612. *stp++ = digit + '0';
  613. val -= digit * 1000;
  614.  
  615. digit = val / 100;
  616. *stp++ = digit + '0';
  617. val -= digit * 100;
  618.  
  619. digit = val / 10;
  620. *stp++ = digit + '0';
  621. val -= digit * 10;
  622. *stp++ = val + '0';
  623. return stp;
  624. }
  625.  
  626. std::string itostr(int input) {
  627.  
  628. buf_t buf[16];
  629.  
  630. if(input == INT_MIN)
  631. return std::string("-2147483648");
  632.  
  633. // handle negative
  634. unsigned val = input;
  635. if(input < 0)
  636. val = -input;
  637.  
  638. buf[0] = '0';
  639. buf_t* endp = reduce(val, buf+1);
  640. *endp = 127;
  641.  
  642. buf_t * stp = buf+1;
  643. while (*stp == '0')
  644. stp++;
  645. if (stp == endp)
  646. stp--;
  647.  
  648. if (input < 0) {
  649. stp--;
  650. *stp = '-';
  651. }
  652. return std::string(stp, endp);
  653. }
  654.  
  655. std::string itostr(unsigned input) {
  656.  
  657. buf_t buf[16];
  658.  
  659. unsigned val = input;
  660. buf_t* endp = reduce(val, buf);
  661. *endp = 127;
  662.  
  663. buf_t * stp = buf;
  664. while (*stp == '0')
  665. stp++;
  666. if (stp == endp)
  667. stp--;
  668.  
  669. return std::string(stp, endp);
  670. }
  671.  
  672. }
  673.  
  674. namespace user {
  675.  
  676. const char digit_pairs[201] = {
  677. "00010203040506070809"
  678. "10111213141516171819"
  679. "20212223242526272829"
  680. "30313233343536373839"
  681. "40414243444546474849"
  682. "50515253545556575859"
  683. "60616263646566676869"
  684. "70717273747576777879"
  685. "80818283848586878889"
  686. "90919293949596979899"
  687. };
  688.  
  689.  
  690. std::string& itostr(int n, std::string& s)
  691. {
  692. if(n==0)
  693. {
  694. s="0";
  695. return s;
  696. }
  697.  
  698. int sign = -(n<0);
  699. unsigned int val = (n^sign)-sign;
  700.  
  701. int size;
  702. if(val>=10000)
  703. {
  704. if(val>=10000000)
  705. {
  706. if(val>=1000000000)
  707. size=10;
  708. else if(val>=100000000)
  709. size=9;
  710. else
  711. size=8;
  712. }
  713. else
  714. {
  715. if(val>=1000000)
  716. size=7;
  717. else if(val>=100000)
  718. size=6;
  719. else
  720. size=5;
  721. }
  722. }
  723. else
  724. {
  725. if(val>=100)
  726. {
  727. if(val>=1000)
  728. size=4;
  729. else
  730. size=3;
  731. }
  732. else
  733. {
  734. if(val>=10)
  735. size=2;
  736. else
  737. size=1;
  738. }
  739. }
  740. size -= sign;
  741. s.resize(size);
  742. char* c = &s[0];
  743. if(sign)
  744. *c='-';
  745.  
  746. c += size-1;
  747. while(val>=100)
  748. {
  749. int pos = val % 100;
  750. val /= 100;
  751. *(short*)(c-1)=*(short*)(digit_pairs+2*pos);
  752. c-=2;
  753. }
  754. while(val>0)
  755. {
  756. *c--='0' + (val % 10);
  757. val /= 10;
  758. }
  759. return s;
  760. }
  761.  
  762.  
  763. std::string& itostr(unsigned val, std::string& s)
  764. {
  765. if(val==0)
  766. {
  767. s="0";
  768. return s;
  769. }
  770.  
  771. int size;
  772. if(val>=10000)
  773. {
  774. if(val>=10000000)
  775. {
  776. if(val>=1000000000)
  777. size=10;
  778. else if(val>=100000000)
  779. size=9;
  780. else
  781. size=8;
  782. }
  783. else
  784. {
  785. if(val>=1000000)
  786. size=7;
  787. else if(val>=100000)
  788. size=6;
  789. else
  790. size=5;
  791. }
  792. }
  793. else
  794. {
  795. if(val>=100)
  796. {
  797. if(val>=1000)
  798. size=4;
  799. else
  800. size=3;
  801. }
  802. else
  803. {
  804. if(val>=10)
  805. size=2;
  806. else
  807. size=1;
  808. }
  809. }
  810.  
  811. s.resize(size);
  812. char* c = &s[size-1];
  813. while(val>=100)
  814. {
  815. int pos = val % 100;
  816. val /= 100;
  817. *(short*)(c-1)=*(short*)(digit_pairs+2*pos);
  818. c-=2;
  819. }
  820. while(val>0)
  821. {
  822. *c--='0' + (val % 10);
  823. val /= 10;
  824. }
  825. return s;
  826. }
  827.  
  828.  
  829. template <typename T>
  830. std::string itostr(T t) {
  831. std::string ret;
  832. itostr(t, ret);
  833. return ret;
  834. }
  835.  
  836. }
  837.  
  838. namespace timo {
  839.  
  840. const char digit_pairs[201] = {
  841. "00010203040506070809"
  842. "10111213141516171819"
  843. "20212223242526272829"
  844. "30313233343536373839"
  845. "40414243444546474849"
  846. "50515253545556575859"
  847. "60616263646566676869"
  848. "70717273747576777879"
  849. "80818283848586878889"
  850. "90919293949596979899"
  851. };
  852.  
  853. static const int BUFFER_SIZE = 11;
  854.  
  855. std::string itostr(int val)
  856. {
  857. char buf[BUFFER_SIZE];
  858. char *it = &buf[BUFFER_SIZE-2];
  859.  
  860. if(val>=0) {
  861. int div = val/100;
  862. while(div) {
  863. memcpy(it,&digit_pairs[2*(val-div*100)],2);
  864. val = div;
  865. it-=2;
  866. div = val/100;
  867. }
  868. memcpy(it,&digit_pairs[2*val],2);
  869. if(val<10)
  870. it++;
  871. } else {
  872. int div = val/100;
  873. while(div) {
  874. memcpy(it,&digit_pairs[-2*(val-div*100)],2);
  875. val = div;
  876. it-=2;
  877. div = val/100;
  878. }
  879. memcpy(it,&digit_pairs[-2*val],2);
  880. if(val<=-10)
  881. it--;
  882. *it = '-';
  883. }
  884.  
  885. return std::string(it,&buf[BUFFER_SIZE]-it);
  886. }
  887.  
  888. std::string itostr(unsigned int val)
  889. {
  890. char buf[BUFFER_SIZE];
  891. char *it = (char*)&buf[BUFFER_SIZE-2];
  892.  
  893. int div = val/100;
  894. while(div) {
  895. memcpy(it,&digit_pairs[2*(val-div*100)],2);
  896. val = div;
  897. it-=2;
  898. div = val/100;
  899. }
  900. memcpy(it,&digit_pairs[2*val],2);
  901. if(val<10)
  902. it++;
  903.  
  904. return std::string((char*)it,(char*)&buf[BUFFER_SIZE]-(char*)it);
  905. }
  906.  
  907. }
  908.  
  909. #define TEST(x, n) \
  910. stringstream ss; \
  911. string s = n::itostr(x); \
  912. ss << (long long)x; \
  913. if (ss.str() != s) { \
  914. passed = false; \
  915. break; \
  916. }
  917.  
  918. #define test(x) { \
  919. passed = true; \
  920. if (0 && passed) { \
  921. char c = CHAR_MIN; \
  922. do { \
  923. TEST(c, x); \
  924. } while (c++ != CHAR_MAX); \
  925. if (!passed) cout << #x << " failed char!!!" << endl; \
  926. /*if (passed) cout << #x << " passed char" << endl;*/ \
  927. } \
  928. if (0 && passed) { \
  929. short c = numeric_limits<short>::min(); \
  930. do { \
  931. TEST(c, x); \
  932. } while (c++ != numeric_limits<short>::max()); \
  933. if (!passed) cout << #x << " failed short!!!" << endl; \
  934. /*if (passed) cout << #x << " passed short" << endl;*/ \
  935. } \
  936. if (passed) { \
  937. int c = numeric_limits<int>::min(); \
  938. do { \
  939. TEST(c, x); \
  940. } while ((c += 100000) < numeric_limits<int>::max() - 100000); \
  941. if (!passed) cout << #x << " failed int!!!" << endl; \
  942. /*if (passed) cout << #x << " passed int" << endl; */\
  943. } \
  944. if (passed) { \
  945. unsigned c = numeric_limits<unsigned>::max(); \
  946. do { \
  947. TEST(c, x); \
  948. } while ((c -= 100000) > 100000); \
  949. if (!passed) cout << #x << " failed unsigned int!!!" << endl; \
  950. /*if (passed) cout << #x << " passed unsigned int" << endl;*/ \
  951. } \
  952. }
  953.  
  954. #define time(x) \
  955. if (passed) { \
  956. cout << #x << ": "; \
  957. progress_timer t; \
  958. unsigned s = 0; \
  959. if (do_time) { \
  960. for (int n = 0; n < N1; n++) { \
  961. int i = 0; \
  962. while (i < N2) { \
  963. i += x::itostr(N2 - i).size() * mult; \
  964. i += x::itostr(i - N2).size() * mult; \
  965. } \
  966. s += i / mult; \
  967. } \
  968. } \
  969. k += s; \
  970. cout << s / double(t.elapsed()) * CLOCKS_PER_SEC / 1000000 << " MB/sec --- "; \
  971. }
  972.  
  973.  
  974. int N1 = 1, N2 = 1000000000;
  975.  
  976. int mult = 1; // used to stay under timelimit on ideone
  977. unsigned long long k = 0;
  978.  
  979. int main(int argc, char** argv) {
  980. bool do_time = 1, do_test = 1;
  981. cin >> mult;
  982.  
  983. bool passed = true;
  984.  
  985. {
  986. if (do_test) test(hopman_fun);
  987. if (do_time) time(hopman_fun);
  988. }
  989. {
  990. if (do_test) test(hopman_fast);
  991. if (do_time) time(hopman_fast);
  992. }
  993. {
  994. if (do_test) test(voigt);
  995. if (do_time) time(voigt);
  996. }
  997. {
  998. if (do_test) test(user_voigt_timo);
  999. if (do_time) time(user_voigt_timo);
  1000. }
  1001. {
  1002. if (do_test) test(timo);
  1003. if (do_time) time(timo);
  1004. }
  1005. {
  1006. if (do_test) test(user);
  1007. if (do_time) time(user);
  1008. }
  1009. {
  1010. if (do_test) test(ergosys);
  1011. if (do_time) time(ergosys);
  1012. }
  1013. return k;
  1014. }
  1015.  
  1016.  
stdin
17
compilation info
prog.cpp: In function ‘std::string hopman_fun::itostr(T) [with T = char]’:
prog.cpp:986:   instantiated from here
prog.cpp:216: warning: unused variable ‘str’
prog.cpp:216: warning: unused variable ‘u2’
prog.cpp:216: warning: unused variable ‘u4’
prog.cpp:216: warning: unused variable ‘u8’
prog.cpp: In function ‘std::string hopman_fun::itostr(T) [with T = short int]’:
prog.cpp:986:   instantiated from here
prog.cpp:216: warning: unused variable ‘str’
prog.cpp:216: warning: unused variable ‘u2’
prog.cpp:216: warning: unused variable ‘u4’
prog.cpp:216: warning: unused variable ‘u8’
prog.cpp: In function ‘std::string hopman_fun::itostr(T) [with T = int]’:
prog.cpp:986:   instantiated from here
prog.cpp:216: warning: unused variable ‘str’
prog.cpp:216: warning: unused variable ‘u2’
prog.cpp:216: warning: unused variable ‘u4’
prog.cpp:216: warning: unused variable ‘u8’
prog.cpp: In function ‘std::string hopman_fun::itostr(T) [with T = unsigned int]’:
prog.cpp:986:   instantiated from here
prog.cpp:216: warning: unused variable ‘str’
prog.cpp:216: warning: unused variable ‘u2’
prog.cpp:216: warning: unused variable ‘u4’
prog.cpp:216: warning: unused variable ‘u8’
prog.cpp: In function ‘std::string voigt::itostr(T) [with T = char]’:
prog.cpp:994:   instantiated from here
prog.cpp:593: warning: statement has no effect
prog.cpp: In function ‘std::string voigt::itostr(T) [with T = short int]’:
prog.cpp:994:   instantiated from here
prog.cpp:593: warning: statement has no effect
prog.cpp: In function ‘std::string voigt::itostr(T) [with T = int]’:
prog.cpp:994:   instantiated from here
prog.cpp:593: warning: statement has no effect
prog.cpp: In function ‘std::string voigt::itostr(T) [with T = unsigned int]’:
prog.cpp:994:   instantiated from here
prog.cpp:593: warning: statement has no effect
prog.cpp: In static member function ‘static std::string voigt::itostr_impl<T, is_signed, 32u>::cvt(T) [with T = int, bool is_signed = true]’:
prog.cpp:594:   instantiated from ‘std::string voigt::itostr(T) [with T = int]’
prog.cpp:994:   instantiated from here
prog.cpp:539: warning: comparison between signed and unsigned integer expressions
prog.cpp:574: warning: label ‘d10000000’ defined but not used
prog.cpp: In static member function ‘static std::string voigt::itostr_impl<T, is_signed, 32u>::cvt(T) [with T = unsigned int, bool is_signed = false]’:
prog.cpp:594:   instantiated from ‘std::string voigt::itostr(T) [with T = unsigned int]’
prog.cpp:994:   instantiated from here
prog.cpp:527: warning: comparison between signed and unsigned integer expressions
prog.cpp:574: warning: label ‘d10000000’ defined but not used
stdout
0.000 s
hopman_fun: 57.6701  MB/sec --- 1.020 s
hopman_fast: 65.3595  MB/sec --- 0.900 s
voigt: 59.4177  MB/sec --- 0.990 s
user_voigt_timo: 47.824  MB/sec --- 1.230 s
timo: 67.6133  MB/sec --- 0.870 s
user: 48.6145  MB/sec --- 1.210 s
ergosys: 58.8235  MB/sec --- 1.000 s