代码

#define TAILMASK 1
/* wc2017b2 lab variant: equality formulation + byte accumulator + budgeted
 * prefetch on an unrolled-by-16-word body.
 *
 * Trick 1 (equality): with b' = (b-1) mod 3, "a beats b" <=> a == b'.  Coding
 * each symbol in 2 bits, equality is (~A1 ^ B1) & (~A0 ^ B0); storing the two
 * *complemented* A planes turns winmask's 7 boolean ops into 2 xor + 1 and.
 * Trick 2: the pshufb popcount result is a per-byte count <= 8, so 31 of them
 * fit in a byte -> accumulate with vpaddb and do the vpsadbw/vpaddq reduction
 * once per 28 iterations.
 * Trick 3: unroll 16 words with 2 T0 prefetches per stream per body (one line
 * each) - the four plane streams are ~MB apart and the HW prefetcher does not
 * keep up on its own.
 */
#include <immintrin.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

typedef unsigned long long u64;
typedef unsigned u32;

#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC push_options
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3")
#endif

#ifndef PFD
#define PFD 32
#endif
#ifndef PFH
#define PFH _MM_HINT_T0
#endif
#ifndef PFN
#define PFN 2
#endif
#ifndef UNROLL
#define UNROLL 112              /* words per byte-accumulator block (28 iters) */
#endif

#define WORDS(n) (((n) + 63) / 64 + 3)
#define ASMLOAD 1

static inline __m256i pc256(__m256i v) {
    const __m256i lut = _mm256_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
                                         0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
    const __m256i m = _mm256_set1_epi8(0x0f);
    __m256i lo = _mm256_and_si256(v, m);
    __m256i hi = _mm256_and_si256(_mm256_srli_epi16(v, 4), m);
    return _mm256_add_epi8(_mm256_shuffle_epi8(lut, lo), _mm256_shuffle_epi8(lut, hi));
}

static inline __m256i LD(const u64 *p) {
#if ASMLOAD
    __m256i v;
    __asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m256i *)(const void *)p));
    return v;
#else
    return _mm256_loadu_si256((const __m256i *)(const void *)p);
#endif
}

void solve(int n, int q, char *s1, char *s2, int *q_x, int *q_y, int *q_len, unsigned *ans) {
    if (q <= 0) return;
    if (n <= 4096) {
        for (int t = 0; t < q; t++) {
            int x = q_x[t], y = q_y[t], l = q_len[t];
            u32 c = 0;
            for (int i = 0; i < l; i++) {
                int a = s1[x + i] - '0', b = s2[y + i] - '0';
                c += (b == (a + 1) % 3);
            }
            ans[t] = c;
        }
        return;
    }
    int W = WORDS(n);
    u64 *A[2], *B[2];
    for (int c = 0; c < 2; c++) {
        A[c] = (u64 *)calloc((size_t)W, 8);
        B[c] = (u64 *)calloc((size_t)W, 8);
    }
    if (!A[0] || !A[1] || !B[0] || !B[1]) { for (int t = 0; t < q; t++) ans[t] = 0; return; }
    /* A[0] = (s1 != 0), A[1] = (s1 != 1)   [complemented planes]
       B[0] = (s2' == 0), B[1] = (s2' == 1) with s2' = (s2-1) mod 3          */
    for (int i = 0; i < n; i++) {
        int a = s1[i] - '0';
        u64 bit = 1ull << (i & 63);
        if (a != 0) A[0][i >> 6] |= bit;
        if (a != 1) A[1][i >> 6] |= bit;
    }
    for (int i = 0; i < n; i++) {
        int b = s2[i] - '0' - 1; if (b < 0) b += 3;
        u64 bit = 1ull << (i & 63);
        if (b == 0) B[0][i >> 6] |= bit;
        else if (b == 1) B[1][i >> 6] |= bit;
    }
    int *urep = (int *)malloc((size_t)q * sizeof(int));
    int *uq = (int *)malloc((size_t)q * sizeof(int));
    if (!urep || !uq) { for (int t = 0; t < q; t++) ans[t] = 0; return; }
    int nu = q;
    for (int t = 0; t < q; t++) { urep[t] = t; uq[t] = t; }
#define BKEY(x, y) ((((x) & 63) << 6) | ((y) & 63))
    int cntb[4097];
    memset(cntb, 0, sizeof(cntb));
    for (int u = 0; u < nu; u++) { int t = uq[u]; cntb[BKEY(q_x[t], q_y[t])]++; }
    int off[4097];
    int s = 0;
    for (int k = 0; k < 4096; k++) { off[k] = s; s += cntb[k]; }
    off[4096] = s;
    int *ord = (int *)malloc((size_t)nu * sizeof(int));
    if (!ord) { for (int t = 0; t < q; t++) ans[t] = 0; return; }
    {
        int pos[4096];
        memcpy(pos, off, sizeof(pos));
        for (int u = 0; u < nu; u++) { int t = uq[u]; ord[pos[BKEY(q_x[t], q_y[t])]++] = t; }
    }
    /* compact per-query records laid out in bucket order: the generic
       q_x/q_y/q_len indirection costs a cache miss per query on the critical
       path (measured ~415 cycles/query, 18% of the run). */
    typedef struct { int x, y, l, qi; } Rec;
    Rec *rec = (Rec *)malloc((size_t)nu * sizeof(Rec));
    if (!rec) { for (int t = 0; t < q; t++) ans[t] = 0; return; }
    for (int t = 0; t < nu; t++) {
        int qi = ord[t];
        rec[t].x = q_x[qi]; rec[t].y = q_y[qi]; rec[t].l = q_len[qi]; rec[t].qi = qi;
    }
    u64 *SA[128], *SB[128];
    for (int c = 0; c < 2; c++) {
        for (int sh = 0; sh < 64; sh++) {
            SA[c * 64 + sh] = (u64 *)_mm_malloc((size_t)W * 8, 32);
            SB[c * 64 + sh] = (u64 *)_mm_malloc((size_t)W * 8, 32);
            u64 *d = SA[c * 64 + sh], *e = SB[c * 64 + sh];
            const u64 *a = A[c], *b = B[c];
            if (sh == 0) { memcpy(d, a, (size_t)W * 8); memcpy(e, b, (size_t)W * 8); }
            else {
                for (int k = 0; k < W - 1; k++) {
                    d[k] = (a[k] >> sh) | (a[k + 1] << (64 - sh));
                    e[k] = (b[k] >> sh) | (b[k + 1] << (64 - sh));
                }
            }
        }
    }
    /* masked tail: one final 4-word iteration with the out-of-range words and
       the trailing bits zeroed, replacing the scalar tail loop + rem word */
    static __m256i tailmask[4 * 64];
    for (int left = 0; left < 4; left++)
        for (int remt = 0; remt < 64; remt++) {
            u64 mv[4];
            for (int v = 0; v < 4; v++)
                mv[v] = (v < left) ? ~0ull : (v == left ? (remt ? ((1ull << remt) - 1) : 0ull) : 0ull);
            tailmask[left * 64 + remt] = _mm256_loadu_si256((const __m256i *)(const void *)mv);
        }
    const __m256i zero = _mm256_setzero_si256();

    for (int g = 0; g < 4096; g++) {
        int b0 = off[g], b1 = off[g + 1];
        if (b0 >= b1) continue;
        int rx = g >> 6, ry = g & 63;
        const u64 *SA0 = SA[rx], *SA1 = SA[64 + rx], *SB0 = SB[ry], *SB1 = SB[64 + ry];
        for (int t = b0; t < b1; t++) {
            const Rec *R = &rec[t];
            int qi = R->qi;
            int x = R->x, y = R->y, l = R->l;
            const u64 *p0 = SA0 + (x >> 6), *p1 = SA1 + (x >> 6);
            const u64 *r0 = SB0 + (y >> 6), *r1 = SB1 + (y >> 6);
            int nw = l >> 6, rem = l & 63;
            __m256i acc = zero, acc8 = zero;
            u32 c = 0;
            int k = (-(x >> 6)) & 3;      /* peel: (x>>6)+k and (y>>6)+k are 32B aligned */
            if (nw < k) k = nw;
            int j = k;
            if (k) {                      /* masked 4-word prologue covering words [0,k) */
                __m256i a0 = LD(p0), a1 = LD(p1), b0v = LD(r0), b1v = LD(r1);
                __m256i m = _mm256_and_si256(_mm256_xor_si256(a1, b1v),
                                             _mm256_xor_si256(a0, b0v));
                m = _mm256_and_si256(m, tailmask[k * 64 + (nw == k ? rem : 0)]);
                acc8 = _mm256_add_epi8(acc8, pc256(m));
            }
            if (!(k && nw == k)) {
            for (; j + UNROLL <= nw; j += UNROLL) {
                for (int u = 0; u < UNROLL; u += 16) {
                    _mm_prefetch((const char *)(p0 + j + u + PFD), PFH);
                    _mm_prefetch((const char *)(p1 + j + u + PFD), PFH);
                    _mm_prefetch((const char *)(r0 + j + u + PFD), PFH);
                    _mm_prefetch((const char *)(r1 + j + u + PFD), PFH);
#if PFN >= 2
                    _mm_prefetch((const char *)(p0 + j + u + PFD + 8), PFH);
                    _mm_prefetch((const char *)(p1 + j + u + PFD + 8), PFH);
                    _mm_prefetch((const char *)(r0 + j + u + PFD + 8), PFH);
                    _mm_prefetch((const char *)(r1 + j + u + PFD + 8), PFH);
#endif
#if PFN >= 3
                    _mm_prefetch((const char *)(p0 + j + u + PFD + 16), PFH);
                    _mm_prefetch((const char *)(p1 + j + u + PFD + 16), PFH);
                    _mm_prefetch((const char *)(r0 + j + u + PFD + 16), PFH);
                    _mm_prefetch((const char *)(r1 + j + u + PFD + 16), PFH);
#endif
#if PFN >= 4
                    _mm_prefetch((const char *)(p0 + j + u + PFD + 24), PFH);
                    _mm_prefetch((const char *)(p1 + j + u + PFD + 24), PFH);
                    _mm_prefetch((const char *)(r0 + j + u + PFD + 24), PFH);
                    _mm_prefetch((const char *)(r1 + j + u + PFD + 24), PFH);
#endif
                    for (int v = 0; v < 16; v += 4) {
                        __m256i a0 = LD(p0 + j + u + v), a1 = LD(p1 + j + u + v);
                        __m256i b0v = LD(r0 + j + u + v), b1v = LD(r1 + j + u + v);
                        __m256i m = _mm256_and_si256(_mm256_xor_si256(a1, b1v),
                                                     _mm256_xor_si256(a0, b0v));
                        acc8 = _mm256_add_epi8(acc8, pc256(m));
                    }
                }
                acc = _mm256_add_epi64(acc, _mm256_sad_epu8(acc8, zero));
                acc8 = zero;
            }
            for (; j + 4 <= nw; j += 4) {
                __m256i a0 = LD(p0 + j), a1 = LD(p1 + j);
                __m256i b0v = LD(r0 + j), b1v = LD(r1 + j);
                __m256i m = _mm256_and_si256(_mm256_xor_si256(a1, b1v),
                                             _mm256_xor_si256(a0, b0v));
                acc8 = _mm256_add_epi8(acc8, pc256(m));
            }
#if TAILMASK
            if ((nw - j) | rem) {
                __m256i a0 = LD(p0 + j), a1 = LD(p1 + j);
                __m256i b0v = LD(r0 + j), b1v = LD(r1 + j);
                __m256i m = _mm256_and_si256(_mm256_xor_si256(a1, b1v),
                                             _mm256_xor_si256(a0, b0v));
                m = _mm256_and_si256(m, tailmask[(nw - j) * 64 + rem]);
                acc8 = _mm256_add_epi8(acc8, pc256(m));
            }
#endif
            }
            acc = _mm256_add_epi64(acc, _mm256_sad_epu8(acc8, zero));
            {
                u64 tmp[4];
                _mm256_storeu_si256((__m256i *)(void *)tmp, acc);
                c += (u32)(tmp[0] + tmp[1] + tmp[2] + tmp[3]);
            }
#if !TAILMASK
            for (; j < nw; j++) {
                u64 mm = (p1[j] ^ r1[j]) & (p0[j] ^ r0[j]);
                c += (u32)__builtin_popcountll(mm);
            }
            if (rem) {
                u64 mm = ((p1[nw] ^ r1[nw]) & (p0[nw] ^ r0[nw])) & ((1ull << rem) - 1);
                c += (u32)__builtin_popcountll(mm);
            }
#endif
            ans[qi] = c;
        }
    }
    for (int t = 0; t < q; t++) { int u = urep[t]; if (uq[u] != t) ans[t] = ans[uq[u]]; }
    for (int c = 0; c < 128; c++) { _mm_free(SA[c]); _mm_free(SB[c]); }
    for (int c = 0; c < 2; c++) { free(A[c]); free(B[c]); }
    free(ord); free(urep); free(uq); free(rec);
}

#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC pop_options
#endif

评测结果