代码

#include <stdint.h>
#include <sys/auxv.h>
#include <unistd.h>
#include <immintrin.h>
#pragma GCC target("avx2")

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

typedef unsigned __int128 u128;
#define FULL ((u128)-1)
#define NB 234496
#define N1 3664
#define N2 58

static u128 blk[NB];
static uint64_t fm1[N1], nm1[N1];
static uint64_t fm2[N2], nm2[N2];
static uint64_t fm3, nm3;

static uint64_t O;
static char *out;

/* ---------- tokenizer buffers ---------- */
#define IBUF_SIZE (32*1024*1024)
#define MAXTOK (3000008)
static char ibuf[IBUF_SIZE + 64];
static uint32_t start_arr[MAXTOK];
static uint8_t  len_arr[MAXTOK];
static uint32_t val_arr[MAXTOK];

static const char *P;

/* ---------- tokenizer ---------- */

static inline void copy_pad(const char *src, char *dst, uint64_t n){
    uint64_t i = 0;
    for (; i + 32 <= n; i += 32){
        _mm256_storeu_si256((__m256i*)(dst + i), _mm256_loadu_si256((const __m256i*)(src + i)));
    }
    for (; i < n; i++) dst[i] = src[i];
    for (int j = 0; j < 64; j++) dst[n + j] = ' ';
}

/* Pass A: SIMD scan -> start_arr / len_arr. returns token count */
static inline uint32_t scan_tokens(const char *p, uint64_t size){
    uint32_t cnt = 0;
    uint32_t carry = 0;      /* prev chunk ended mid-digit */
    uint32_t run_start = 0;
    const __m256i zero_less = _mm256_set1_epi8('0' - 1);
    uint64_t pos = 0;
    for (; pos < size; pos += 32){
        __m256i v = _mm256_loadu_si256((const __m256i*)(p + pos));
        __m256i d = _mm256_cmpgt_epi8(v, zero_less);   /* byte >= '0' */
        uint32_t dm = (uint32_t)_mm256_movemask_epi8(d);
        uint32_t m = dm;
        if (carry){
            if (m != 0xFFFFFFFFu){
                int first0 = __builtin_ctz(~m);
                len_arr[cnt] = (uint8_t)((uint32_t)(pos - run_start) + (uint32_t)first0);
                start_arr[cnt] = run_start;
                cnt++;
                carry = 0;
                m &= ~((1u << (first0 + 1)) - 1);
            }
        }
        while (m){
            int s = __builtin_ctz(m);
            int len = __builtin_ctz(~(m >> s));
            if (s + len == 32){
                carry = 1;
                run_start = (uint32_t)pos + (uint32_t)s;
                m = 0;
            } else {
                len_arr[cnt] = (uint8_t)len;
                start_arr[cnt] = (uint32_t)pos + (uint32_t)s;
                cnt++;
                m &= ~(((1u << len) - 1) << s);
            }
        }
    }
    if (carry){
        /* number ran to very end of input (no trailing separator) */
        len_arr[cnt] = (uint8_t)((uint32_t)(size - run_start));
        start_arr[cnt] = run_start;
        cnt++;
    }
    return cnt;
}

/* 8-digit conversion (MSD first), 0 <= L <= 8, right-align with zero pad */
static inline uint32_t conv8(const char *p, int L){
    __m128i v = _mm_loadu_si128((const __m128i*)p);
    __m128i d = _mm_sub_epi8(v, _mm_set1_epi8('0'));
    /* shuf table: right-align L digits into bytes [8-L, 8) of low 8-byte lane */
    static const int8_t sh[9][16] __attribute__((aligned(16))) = {
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {-128,-128,-128,-128,-128,-128,-128,0,  -128,-128,-128,-128,-128,-128,-128,-128},
        {-128,-128,-128,-128,-128,-128,0,1,     -128,-128,-128,-128,-128,-128,-128,-128},
        {-128,-128,-128,-128,-128,0,1,2,        -128,-128,-128,-128,-128,-128,-128,-128},
        {-128,-128,-128,-128,0,1,2,3,           -128,-128,-128,-128,-128,-128,-128,-128},
        {-128,-128,-128,0,1,2,3,4,              -128,-128,-128,-128,-128,-128,-128,-128},
        {-128,-128,0,1,2,3,4,5,                 -128,-128,-128,-128,-128,-128,-128,-128},
        {-128,0,1,2,3,4,5,6,                    -128,-128,-128,-128,-128,-128,-128,-128},
        {0,1,2,3,4,5,6,7,                        -128,-128,-128,-128,-128,-128,-128,-128},
    };
    __m128i a = _mm_shuffle_epi8(d, _mm_load_si128((const __m128i*)sh[L]));
    __m128i m = _mm_maddubs_epi16(a, _mm_setr_epi8(10,1,10,1,10,1,10,1,10,1,10,1,10,1,10,1));
    __m128i m2 = _mm_madd_epi16(m, _mm_setr_epi16(100,1,100,1,100,1,100,1));
    __m128i m3 = _mm_mullo_epi32(m2, _mm_setr_epi32(10000,1,10000,1));
    __m128i h = _mm_hadd_epi32(m3, m3);
    return (uint32_t)_mm_cvtsi128_si32(h);
}

static inline uint32_t conv_token(const char *p, uint32_t start, int L){
    if (L <= 8) return conv8(p + start, L);
    /* L == 9 or 10 (only 'a' can exceed 8 digits) */
    int h = p[start] - '0';
    const char *lo = p + start + 1;
    if (L == 10){ h = h * 10 + (p[start+1] - '0'); lo = p + start + 2; }
    return (uint32_t)h * 100000000u + conv8(lo, 8);
}

static inline void convert_all(const char *p, uint32_t cnt){
    for (uint32_t i = 0; i < cnt; i++){
        uint32_t start = start_arr[i];
        int L = len_arr[i];
        uint32_t v = conv_token(p, start, L);
        if (start && p[start - 1] == '-') v = (uint32_t)(-(int32_t)v);
        val_arr[i] = v;
    }
}


__attribute__((noreturn)) static void done(uint64_t olen, struct DuckInfo *di, int use_di){
    if (use_di) di->stdout_size = olen;
    else (void)!write(1, out, olen);
    asm volatile("mov $60, %%eax; xor %%edi, %%edi; syscall" ::: "rax","rdi","memory");
    __builtin_unreachable();
}

int main(){
    struct DuckInfo *di = (struct DuckInfo*)getauxval(0x6b637564);
    uint64_t size;
    const char *src;
    int use_di = 0;
    if (di && di->abi_version >= 1 && di->stdin_ptr && di->stdout_ptr){
        size = di->stdin_size; src = di->stdin_ptr; out = di->stdout_ptr; use_di = 1;
        copy_pad(src, ibuf, size);
    } else {
        long n2 = 0, t;
        while (n2 < IBUF_SIZE && (t = read(0, ibuf + n2, IBUF_SIZE - n2)) > 0) n2 += t;
        size = (uint64_t)n2;
        for (int j = 0; j < 64; j++) ibuf[n2 + j] = ' ';
        src = ibuf;
        static char obuf[1<<22];
        out = obuf;
    }
    P = ibuf;

    uint32_t cnt = scan_tokens(ibuf, size);
    convert_all(ibuf, cnt);

    int n = (int32_t)val_arr[0];
    uint32_t idx = 4;
    uint64_t acc = 0;
    for (int i = 0; i < n; i++){
        int op = (int32_t)val_arr[idx++];
        if (op == 1){
            int a = (int32_t)val_arr[idx++];
            int b = (int32_t)val_arr[idx++];
            acc += (uint64_t)(a < 0 ? -(int64_t)a : a) + (uint64_t)b;
        } else {
            int k = (int32_t)val_arr[idx++];
            acc += (uint64_t)k;
            out[O++] = (char)('0' + (acc & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, use_di);
}

评测结果