Codeforces Round #270: G. Design Tutorial: Increase the Constraints
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;
}