fork(24) 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
https://ideone.com/XZRqp
language:
C++ (gcc 8.3)
created:
13 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!