ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1369. Cockroach Race

custom 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 funlock _unlock_file
#else
#define uputchar putchar_unlocked
#define ugetchar getchar_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
{
//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 >
{
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 >
{
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 >
{
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;"
"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');
}
}

}