ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1369. Тараканьи бега

custom input to get AC 0.483 and 1 984 KB memory (~26ms for ~2.25MB input)
Послано Orient 10 апр 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');
    }
}

}