代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


/*
 * NOIP 2017 "time complexity".  The judge exposes stdin/stdout as memory;
 * parsing it in place avoids the stdio and process-startup overhead that
 * dominates this small input.
 */
__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const unsigned char *p = (const unsigned char *)info->stdin_ptr;
    char *out = info->stdout_ptr;

    while ((unsigned)(*p - '0') > 9) ++p;
    unsigned tests = 0;
    do tests = tests * 10 + *p++ - '0'; while ((unsigned)(*p - '0') <= 9);

    do {
        while ((unsigned)(*p - '0') > 9) ++p;
        unsigned lines = 0;
        do lines = lines * 10 + *p++ - '0'; while ((unsigned)(*p - '0') <= 9);

        while (*p != 'O') ++p;
        p += 2;                         /* O( */
        unsigned wanted = 0;
        if (*p == 'n') {
            p += 2;                     /* n^ */
            do wanted = wanted * 10 + *p++ - '0';
            while ((unsigned)(*p - '0') <= 9);
        } else {
            ++p;                        /* 1 */
        }
        ++p;                            /* ) */

        unsigned active = 0;
        unsigned depth = 0;
        unsigned dead = 0;
        unsigned degree = 0;
        unsigned maximum = 0;
        unsigned error = 0;
        unsigned char stack_var[104];
        unsigned char stack_flags[104]; /* bit 0: adds n; bit 1: starts dead */

        while (lines--) {
            while (*p <= ' ') ++p;
            if (*p == 'E') {
                ++p;
                if (!depth) {
                    error = 1;
                    continue;
                }
                --depth;
                unsigned flags = stack_flags[depth];
                active &= ~(1u << stack_var[depth]);
                degree -= flags & 1u;
                dead -= flags >> 1;
                continue;
            }

            ++p;                        /* F */
            while (*p == ' ') ++p;
            unsigned var = *p++ - 'a';
            if (active & (1u << var)) error = 1;
            active |= 1u << var;

            while (*p == ' ') ++p;
            unsigned xn = *p == 'n';
            unsigned x = 0;
            if (xn) {
                ++p;
            } else {
                do x = x * 10 + *p++ - '0'; while ((unsigned)(*p - '0') <= 9);
            }

            while (*p == ' ') ++p;
            unsigned yn = *p == 'n';
            unsigned y = 0;
            if (yn) {
                ++p;
            } else {
                do y = y * 10 + *p++ - '0'; while ((unsigned)(*p - '0') <= 9);
            }

            unsigned flags = 0;
            if (!dead) {
                if ((!xn && !yn && x > y) || (xn && !yn)) {
                    flags = 2;
                    ++dead;
                } else if (!xn && yn) {
                    flags = 1;
                    if (++degree > maximum) maximum = degree;
                }
            }
            stack_var[depth] = (unsigned char)var;
            stack_flags[depth] = (unsigned char)flags;
            ++depth;
        }

        error |= depth != 0;
        if (error) {
            __builtin_memcpy(out, "ERR\n", 4);
            out += 4;
        } else if (maximum == wanted) {
            __builtin_memcpy(out, "Yes\n", 4);
            out += 4;
        } else {
            __builtin_memcpy(out, "No\n", 3);
            out += 3;
        }
    } while (--tests);

    info->stdout_size = (duck_u64)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果