Codeforces Round #270: G. Design Tutorial: Increase the Constraints

,

http://codeforces.com/contest/472/problem/G

SIMDによる嘘解法。 codeforcesはAVXまでしか使えない、かつintrinsicは(ものにもよるだろうがAVXのだと)target specific option mismatchと言われてだめなので注意すること。気付かず書くとcompile errorや実行時にinvalid instructionする。両方踏んだ。

solution

愚直 + SIMD。$O(Q \cdot \mathrm{len})$。

一致比較には'0' = 48, '1' = 49により'0' ^ '1' = 1なのでpvxorを利用した。集計はvpaddbで垂直に足していって、(桁上がりが発生する前の適当なタイミングで)charとして水平に足し合わせた。

implementation

http://codeforces.com/contest/472/submission/24931343

#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
#define LEN_MAX 200000
char a[LEN_MAX+1];
char b[LEN_MAX+1];
int main() {
    int q; scanf("%[01] %[01]%d", a, b, &q);
    for (char *p = a; *p; ++ p) *p = (*p == '1');
    for (char *p = b; *p; ++ p) *p = (*p == '1');
    while (q --) {
        int p1, p2, len; scanf("%d%d%d", &p1, &p2, &len);
        int cnt = 0;
        int i = 0;
        for (; i < len-16; ) {
            __asm__ (
                    "pxor %%xmm1, %%xmm1 ;" :);
            for (int j = 0; j < 127 and i < len-16; ++ j, i += 16) {
                volatile char *pa = a + p1 + i;
                volatile char *pb = b + p2 + i;
                __asm__ (
                        "vmovdqu (%0), %%xmm2 ;"
                        "vmovdqu (%1), %%xmm3 ;"
                        "vpxor %%xmm2, %%xmm3, %%xmm2 ;"
                        "vpaddb %%xmm1, %%xmm2, %%xmm1 ;"
                        : : "r" (pa), "r" (pb));
            }
            volatile char acc[16];
            __asm__ (
                    "vmovdqu %%xmm1, (%0) ;"
                    : : "r" (acc));
            repeat (k,16) cnt += acc[k];
        }
        for (; i < len; ++ i) if (a[p1 + i] != b[p2 + i]) ++ cnt;
        printf("%d\n", cnt);
    }
    return 0;
}