代码

#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


enum { MAXN = 50000, MAXM = 100000, MAXV = MAXN * 2, MAXE = MAXM * 2 };

typedef struct { int x, y; unsigned char a, b; } Rule;
static Rule rules[MAXM];
static int head[MAXV], to[MAXE], next_edge[MAXE];
static int dfn[MAXV], low[MAXV], stack[MAXV], component[MAXV];
static unsigned char on_stack[MAXV], blocked[MAXN], original[MAXN];
static int timer, stack_size, component_count, edge_count;

static __attribute__((always_inline)) inline void add_edge(int u, int v) {
    to[edge_count] = v;
    next_edge[edge_count] = head[u];
    head[u] = edge_count++;
}

static __attribute__((noinline)) void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stack[stack_size++] = u;
    on_stack[u] = 1;
    for (int e = head[u]; e != -1; e = next_edge[e]) {
        int v = to[e];
        if (!dfn[v]) {
            tarjan(v);
            if (low[v] < low[u]) low[u] = low[v];
        } else if (on_stack[v] && dfn[v] < low[u]) {
            low[u] = dfn[v];
        }
    }
    if (low[u] == dfn[u]) {
        for (;;) {
            int v = stack[--stack_size];
            on_stack[v] = 0;
            component[v] = component_count;
            if (v == u) break;
        }
        ++component_count;
    }
}

static __attribute__((always_inline)) inline int literal(int position, unsigned car) {
    unsigned first = blocked[position] == 0 ? 1u : 0u;
    return position + position + (car != first);
}

static int solve_mask(int n, int mask, const int *wild, int wild_count) {
    for (int i = 0; i < wild_count; ++i) blocked[wild[i]] = (mask >> i) & 1;
    for (int i = 0; i < n + n; ++i) head[i] = -1;
    edge_count = 0;
    for (int i = 0; i < MAXM && rules[i].x >= 0; ++i) {
        Rule *r = rules + i;
        if (blocked[r->x] == r->a) continue;
        int from = literal(r->x, r->a);
        if (blocked[r->y] == r->b) {
            add_edge(from, from ^ 1);
        } else {
            int dest = literal(r->y, r->b);
            add_edge(from, dest);
            add_edge(dest ^ 1, from ^ 1);
        }
    }
    for (int i = 0; i < n + n; ++i) dfn[i] = 0, on_stack[i] = 0;
    timer = stack_size = component_count = 0;
    for (int i = 0; i < n + n; ++i) if (!dfn[i]) tarjan(i);
    for (int i = 0; i < n; ++i)
        if (component[i + i] == component[i + i + 1]) return 0;
    return 1;
}

static void solve(DuckInfo *info) {
    const char *in = info->stdin_ptr;
    int n = (int)duck_read_u64(&in);
    int wild_count = (int)duck_read_u64(&in);
    while (*in <= ' ') ++in;
    int wild[8], seen = 0;
    for (int i = 0; i < n; ++i) {
        unsigned c = (unsigned)(*in++ - 'a');
        original[i] = (unsigned char)c;
        if (c == 23) wild[seen++] = i;
        else blocked[i] = (unsigned char)c;
    }
    int m = (int)duck_read_u64(&in);
    for (int i = 0; i < m; ++i) {
        rules[i].x = (int)duck_read_u64(&in) - 1;
        while (*in <= ' ') ++in;
        rules[i].a = (unsigned char)(*in++ - 'A');
        rules[i].y = (int)duck_read_u64(&in) - 1;
        while (*in <= ' ') ++in;
        rules[i].b = (unsigned char)(*in++ - 'A');
    }
    if (m < MAXM) rules[m].x = -1;

    int mask;
    for (mask = 0; mask < (1 << wild_count); ++mask)
        if (solve_mask(n, mask, wild, wild_count)) break;
    char *out = info->stdout_ptr;
    if (mask == (1 << wild_count)) {
        *out++ = '-'; *out++ = '1'; *out++ = '\n';
    } else {
        for (int i = 0; i < n; ++i) {
            unsigned first = blocked[i] == 0 ? 1u : 0u;
            unsigned car = component[i + i] < component[i + i + 1] ? first : 3u - blocked[i] - first;
            *out++ = (char)('A' + car);
        }
        *out++ = '\n';
    }
    info->stdout_size = (duck_u64)(out - info->stdout_ptr);
}

#ifdef LOCAL
#include <stdio.h>
int main(void) {
    static char input[4000000], output[100000]; DuckInfo info = {0};
    info.stdin_size = fread(input, 1, sizeof input, stdin); info.stdin_ptr = input;
    info.stdout_ptr = output; solve(&info); fwrite(output, 1, info.stdout_size, stdout);
    return 0;
}
#else
__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused; DuckInfo *info = duck_info(argc, argv); solve(info); duck_exit();
}
int main(void) {}
#endif

评测结果