代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2017 时间复杂度: parse the nested loops, detect ERR (unbalanced F/E or
// duplicate live variable) and compare the real exponent with the claimed one.
typedef unsigned long long u64;
struct DuckInfo {
    u64 abi;
    const char *in; u64 in_size;
    char *out; u64 out_limit; u64 out_size;
    char *err; u64 err_limit; u64 err_size;
    const char *ib; u64 ib_limit;
    char *ob; u64 ob_limit; u64 tsc;
} __attribute__((packed));

static const char *sk(const char *p) {
    while (*p == ' ' || *p == '\n' || *p == '\r' || *p == '\t') p++;
    return p;
}
static int num(const char **pp) {
    int v = 0;
    while (**pp >= '0' && **pp <= '9') v = v * 10 + (*(*pp)++ - '0');
    return v;
}

int main(void) { return 0; }

void __libc_start_main(int (*mf)(int, char **, char **), int ac, char **av) {
    (void)mf;
    struct DuckInfo *d = (struct DuckInfo *)((u64 *)av)[29];
    const char *p = d->in;
    char *o = d->out;
    p = sk(p);
    int t = num(&p);
    struct Frame { unsigned char var, isn, isdead, contrib; } stk[128];
    while (t--) {
        p = sk(p);
        int L = num(&p);
        p = sk(p);
        /* "O(...)" */
        p++;                 /* O */
        p++;                 /* ( */
        int expw = 0;
        if (*p == 'n') {
            p++;
            if (*p == '^') { p++; expw = num(&p); }
        } else {
            p++;             /* '1' */
        }
        p++;                 /* ')' */
        unsigned char alive[256];
        for (int i = 0; i < 256; i++) alive[i] = 0;
        int top = 0, dead = 0, cur = 0, maxc = 0, err = 0;
        for (int i = 0; i < L; i++) {
            p = sk(p);
            char c = *p++;
            if (c == 'F') {
                p = sk(p);
                unsigned char var = (unsigned char)*p++;
                p = sk(p);
                int xisn = (*p == 'n');
                int xv = 0;
                if (xisn) p++; else xv = num(&p);
                p = sk(p);
                int yisn = (*p == 'n');
                int yv = 0;
                if (yisn) p++; else yv = num(&p);
                int isdead = 0, isn = 0;
                if (!xisn && yisn) isn = 1;
                else if (xisn && !yisn) isdead = 1;
                else if (!xisn && !yisn && xv > yv) isdead = 1;
                if (alive[var]) err = 1;
                alive[var] = 1;
                int contrib = isn && (dead == 0);
                stk[top].var = var; stk[top].isn = (unsigned char)isn;
                stk[top].isdead = (unsigned char)isdead; stk[top].contrib = (unsigned char)contrib;
                top++;
                if (isdead) dead++;
                if (contrib) { cur++; if (cur > maxc) maxc = cur; }
            } else {
                if (top == 0) { err = 1; }
                else {
                    top--;
                    struct Frame f = stk[top];
                    alive[f.var] = 0;
                    if (f.isdead) dead--;
                    if (f.contrib) cur--;
                }
            }
        }
        if (top) err = 1;
        if (err) { o[0]='E'; o[1]='R'; o[2]='R'; o[3]='\n'; o += 4; }
        else if (maxc == expw) { o[0]='Y'; o[1]='e'; o[2]='s'; o[3]='\n'; o += 4; }
        else { o[0]='N'; o[1]='o'; o[2]='\n'; o += 3; }
    }
    d->out_size = (u64)(o - d->out);
    __asm__ volatile("mov $60,%%eax; xor %%edi,%%edi; syscall" ::: "rax","rdi","rcx","r11","memory");
    __builtin_unreachable();
}

评测结果