代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2017 时间复杂度: parse nested F/E loops directly from the DuckInfo buffer.
// A loop F i x y adds n to the live nesting depth iff x is numeric and y is "n";
// if x is "n" and y numeric, or both numeric with x>y, the loop body is dead.
// The live-variable set detects duplicate-variable / unbalanced ERR.
typedef unsigned long long u64;
struct DuckInfo {
    u64 abi; const char *in; u64 in_size; char *out; u64 out_limit, out_size;
    char *err; u64 err_limit, err_size; const char *IB; u64 IB_limit;
    char *OB; u64 OB_limit; u64 tsc;
} __attribute__((packed));

static inline const char *skip(const char *p) {
    while (*p == ' ' || *p == '\n' || *p == '\r' || *p == '\t') ++p;
    return p;
}

static int run(const char *in, char *out) {
    const char *p = in;
    char *o = out;
    int t = 0;
    while (*p >= '0' && *p <= '9') t = t * 10 + (*p++ - '0');
    while (t--) {
        p = skip(p);
        int L = 0;
        while (*p >= '0' && *p <= '9') L = L * 10 + (*p++ - '0');
        p = skip(p) + 2;                 // skip "O("
        int expw = 0;
        if (*p == 'n') {
            p += 2;
            while (*p >= '0' && *p <= '9') expw = expw * 10 + (*p++ - '0');
        } else {
            ++p;
        }
        ++p;                             // ')'
        struct Frame { unsigned char v, isn, dead, contrib; } stk[128];
        int top = 0, mask = 0, err = 0, dead = 0, cur = 0, maxc = 0;
        for (int i = 0; i < L; ++i) {
            p = skip(p);
            char c = *p++;
            if (c == 'F') {
                ++p;
                int vi = *p++ - 'a';
                ++p;
                int xnum = (*p != 'n'), xv = 0;
                if (xnum) { xv = *p++ - '0'; if (*p >= '0' && *p <= '9') xv = xv * 10 + (*p++ - '0'); }
                else ++p;
                ++p;
                int ynum = (*p != 'n'), yv = 0;
                if (ynum) { yv = *p++ - '0'; if (*p >= '0' && *p <= '9') yv = yv * 10 + (*p++ - '0'); }
                else ++p;
                int d = 0, isn = 0;
                if (!xnum && ynum) d = 1;
                else if (xnum && !ynum) isn = 1;
                else if (xnum && ynum && xv > yv) d = 1;
                int b = 1 << vi;
                if (mask & b) err = 1;
                mask |= b;
                int contrib = isn && (dead == 0);
                stk[top].v = (unsigned char)vi; stk[top].isn = (unsigned char)isn;
                stk[top].dead = (unsigned char)d; stk[top].contrib = (unsigned char)contrib;
                ++top;
                if (d) ++dead;
                if (contrib && ++cur > maxc) maxc = cur;
            } else {
                if (top == 0) err = 1;
                else {
                    --top;
                    mask &= ~(1 << stk[top].v);
                    if (stk[top].contrib) --cur;
                    if (stk[top].dead) --dead;
                }
            }
        }
        if (top != 0) err = 1;
        if (err) { *o++ = 'E'; *o++ = 'R'; *o++ = 'R'; }
        else if (maxc == expw) { *o++ = 'Y'; *o++ = 'e'; *o++ = 's'; }
        else { *o++ = 'N'; *o++ = 'o'; }
        *o++ = '\n';
    }
    return (int)(o - out);
}

#ifndef LOCAL_TEST
int main(void) { return 0; }
#endif

#ifndef LOCAL_TEST
void __libc_start_main(int (*mf)(int, char **, char **), int ac, char **av) {
    (void)mf; (void)ac;
    struct DuckInfo *d = (struct DuckInfo *)((u64 *)av)[29];
    d->out_size = (u64)run(d->in, d->out);
    __asm__ volatile("mov $60,%%eax; xor %%edi,%%edi; syscall" ::: "rax", "rdi", "memory");
    __builtin_unreachable();
}
#else
#include <stdio.h>
int main(){ static char in[1<<16], out[1<<16]; int n=(int)fread(in,1,sizeof(in)-1,stdin); in[n]=0; int len=run(in,out); fwrite(out,1,len,stdout); return 0; }
#endif

评测结果