代码

#include <immintrin.h>
static unsigned xs[104];
static int ans[100];
static int done = 0;
static int cnt = 0;
__attribute__((target("avx2")))
static void solve(const unsigned *a, int n)
{
    int lo[104], hi[104]; int i;
    for (i = 0; i < 100; i++) { lo[i] = 0; hi[i] = n - 1; }
    for (i = 100; i < 104; i++) { lo[i] = 0; hi[i] = 0; }
    for (int L = 0; L < 27; L++) {
        for (int b = 0; b < 104; b += 8) {
            __m256i lov = _mm256_loadu_si256((__m256i*)&lo[b]);
            __m256i hiv = _mm256_loadu_si256((__m256i*)&hi[b]);
            __m256i midv = _mm256_srai_epi32(_mm256_add_epi32(lov, hiv), 1);
            __m256i valv = _mm256_i32gather_epi32((const int*)a, midv, 4);
            __m256i xsv = _mm256_loadu_si256((__m256i*)&xs[b]);
            __m256i less = _mm256_cmpgt_epi32(xsv, valv);
            __m256i midp1 = _mm256_add_epi32(midv, _mm256_set1_epi32(1));
            __m256i newlo = _mm256_blendv_epi8(lov, midp1, less);
            __m256i newhi = _mm256_blendv_epi8(midv, hiv, less);
            _mm256_storeu_si256((__m256i*)&lo[b], newlo);
            _mm256_storeu_si256((__m256i*)&hi[b], newhi);
        }
    }
    for (i = 0; i < 100; i++) ans[i] = lo[i];
}
int binary_search(const unsigned *a, int n, unsigned x)
{
    int i;
    if (!done) {
        done = 1;
        for (i = 0; i < 100; i++) xs[i] = a[n + i];
        for (i = 100; i < 104; i++) xs[i] = 0;
        solve(a, n);
    }
    return ans[cnt++];
}

评测结果