|
|
back to boardcustom input to get AC 0.483 and 1 984 KB memory (~26ms for ~2.25MB input) Posted by Orient 10 Apr 2018 14:35 If there is a way to improve, let me know: #ifdef __MINGW32__ #define uputchar _putchar_nolock #define ugetchar _getchar_nolock #define ufread _fread_nolock #define funlock _unlock_file #else #define uputchar putchar_unlocked #define ugetchar getchar_unlocked #define ufread fread_unlocked #define funlock funlockfile #endif namespace { #if 1 struct { int c; int operator * () const { return c; } auto & operator ++ () { c = ugetchar(); return *this; } auto operator ++ (int) { auto prev = *this; operator ++ (); return prev; } } cursor; #else char input[(1 << 21) + (1 << 19)]; auto cursor = input; auto input_size = cursor - input; #endif inline void skip_ws() { for (;;) { switch (*++cursor) { case ' ' : case '\t' : case '\r' : case '\n' : break; default : return; } } } inline void read_input() { //std::cin.tie(nullptr); std::ios::sync_with_stdio(false); #if 0 #ifdef ONLINE_JUDGE cursor += ufread(input, sizeof(char), sizeof input, stdin); #else { const char s[] = R"(4 0 0 1 0 0 1 1 2 2 0 0 0 2)"; cursor = std::copy(s, s + sizeof s - 1, cursor); } #endif //assert(cursor < input + sizeof input); //assert(input + 0 != nullptr); input_size = cursor - input; cursor = input - 1; #endif } template< typename U > void read_uint(U & u) { static_assert(std::is_unsigned< U >::value, "!"); u = 0; for (;;) { char c = *cursor; if ((c < '0') || ('9' < c)) { break; } ++cursor; u = (u * 10) + (c - '0'); } } template< typename I > void read_int(I & i) { char sign = *cursor; switch (sign) { case '+' : case '-' : ++cursor; } std::make_unsigned_t< I > u = 0; for (;;) { char c = *cursor; if ((c < '0') || ('9' < c)) { break; } ++cursor; u = (u * 10) + (c - '0'); } i = I(u); if (sign == '-') { i = -i; } } template< typename F > void read_float(F & result) { static_assert(std::is_floating_point< F >::value, "!"); char c = *cursor; std::uint8_t significand[std::numeric_limits< F >::digits10]; auto s = significand; std::int32_t after = 0; std::int32_t before = 0; char sign = c; switch (c) { case '-' : case '+' : c = *++cursor; } [&] { bool d = false; for (;;) { switch (c) { case '.' : before = 1; break; case '0' ... '9' : { if (c != '0') { d = true; } if (0 < before) { ++before; } if (d) { *s++ = (c - '0'); if (s == significand + sizeof significand) { std::int32_t a = 0; for (;;) { switch ((c = *++cursor)) { case '0' ... '9' : ++a; break; case '.' : after = a; break; default : if ((before == 0) && (after == 0)) { after = a; } return; } } } } break; } default : if (!d) { *s++ = 0; } return; } c = *++cursor; } }(); if (0 < before) { after -= (before - 1); } std::uint32_t exponent = 0; switch (c) { case 'e' : case 'E' : { c = *++cursor; char esign = c; switch (c) { case '-' : case '+' : c = *++cursor; break; } [&] { for (;;) { switch (c) { case '0' ... '9' : exponent = (exponent * 10) + (c - '0'); break; default : { return; } } c = *++cursor; } }(); if (esign == '-') { after -= exponent; } else { after += exponent; } } } alignas(32) std::uint8_t bcd[10] = {}; std::uint32_t b = 0; do { --s; if ((b % 2) == 0) { bcd[b / 2] = *s; } else { bcd[b / 2] |= (*s << 4); } ++b; } while (s != significand); if (sign == '-') { bcd[9] = (1 << 7); } asm( "fldl2t;" "fildl %[exp10];" "fmulp;" "fld %%st;" "frndint;" "fxch;" "fsub %%st(1), %%st;" "f2xm1;" "fld1;" "faddp;" "fscale;" "fstp %%st(1);" "fbld %[tbyte];" "fmulp;" : "=t"(result) : [exp10]"m"(after), [tbyte]"m"(bcd) : "st(1)", "st(2)" ); } template< typename I > void print_int(I value) { if (value == 0) { uputchar('0'); return; } std::make_unsigned_t< I > v; if (value < 0) { uputchar('-'); v = decltype(v)(-value); } else { v = decltype(v)(value); } I rev = v; I count = 0; while ((rev % 10) == 0) { ++count; rev /= 10; } rev = 0; while (v != 0) { rev = (rev * 10) + (v % 10); v /= 10; } while (rev != 0) { uputchar("0123456789"[rev % 10]); rev /= 10; } while (0 != count) { --count; uputchar('0'); } } } |
|
|