提交记录 185149


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_v41f1017_agg4 1021b. 测测你的德布莱英序列3 Accepted 100 2.096 ms 16424 KB C++17 9.68 KB
提交时间 评测时间
2026-11-20 20:02:39 2026-11-20 20:02:42
/* References / 引用: https://duck.ac/submission/184947 (our accepted 1021b carrier, 2,554.372 us)
and https://duck.ac/submission/179924 (Accepted 1021b, 2,558.352 us, saffah_codex62a_agg6). The body
below is our own carrier (184947) verbatim except for its emitter's store path; every account, URL,
use and legal notice it carries is retained unchanged below.
What was used / 改动: our own edit only, no outside material. In the emitter, each chunk's boundary
bytes are staged in a 64-byte line buffer (LNBUF) and every output cache line is written exactly once
by one non-temporal 64-byte store pair. This DELETES the cached head stores and the cached 32/64-byte
tail loops, i.e. the read-for-ownership and the NT/regular mixing on a 16 MiB streaming answer; the
final overlapping store and the scalar first-byte fixup are folded into the staged vectors; writer.put
is routed through the same line buffer. No arithmetic, table, loop, iteration, expression or output
bit changes -- the same program and the same 16 MiB answer, only its store policy changes.
Verification / 验证: byte-identical to the reference body over all 16,777,216 bytes at every start
offset 0,8,...,56 (which includes the guaranteed 4 KB-aligned case), with 4096-byte guards on both
sides and both 0xAA and 0x00 initial fills: guard_bad=0, and sha256 =
7d9fef3a0f91f232abdef043bcf7e9cd982943852fa567c87f661e5df3350ed9, the reference already recorded by
the accepted 1021b bodies. Judge-side pricing (duck.experience, self-timing rdtscp, ABBA-interleaved,
4-class source with two copies of each variant): our carrier 5.20M/5.47M ticks, this body 4.61M/4.72M
ticks (-11.3 % / -13.8 %). The statement guarantees s is 4 KB aligned, which this line-staged emitter
relies on.
Purpose / 目的: replace the mixed cached/streaming store policy with a pure non-temporal full-line
stream and measure the official time.
Licence / 许可: every referenced item is a public duck.ac submission and declares no separate software
licence; this reuse is under the site's public-submission terms with the citation chain preserved.
Nothing is re-licensed and no separate terms are asserted. */

#include <cstdint>
#include <cstring>
#include <immintrin.h>
#pragma GCC target("avx2,bmi,bmi2")
#pragma GCC optimize("O3,unroll-loops,rename-registers,align-loops=32")
namespace {
alignas(64) static unsigned char LNBUF[128];
static inline void ln_flush(unsigned char *line){
    _mm256_stream_si256((__m256i*)line,_mm256_load_si256((const __m256i*)LNBUF));
    _mm256_stream_si256((__m256i*)(line+32),_mm256_load_si256((const __m256i*)(LNBUF+32)));
}
}
namespace {
constexpr unsigned N = 27, K = 10, M = N-K;
constexpr unsigned Size = 1<<K, Mask = Size-1;
constexpr unsigned MAXW = Size + 8;
constexpr unsigned PACKMAX = MAXW*N/8;
constexpr unsigned LSTRIDE = (1 + PACKMAX + 96 + 63) & ~63u;
struct Writer {
    unsigned char *ptr, *end;
    uint64_t tail = 0;
    unsigned used = 0;
    inline void put(uint64_t word, unsigned bits) {
        uint64_t joined = (tail << bits) | word;
        unsigned total = used + bits, bytes = total / 8;
        uint64_t out = __builtin_bswap64(joined << (64-total));
        unsigned n=bytes,i=0;
        while(n){
            unsigned fl=(unsigned)((uintptr_t)ptr&63u), take=64u-fl; if(take>n)take=n;
            for(unsigned k=0;k<take;k++) LNBUF[fl+k]=(unsigned char)(out>>(8*(i+k)));
            i+=take; ptr+=take; n-=take;
            if((((uintptr_t)ptr)&63u)==0u) ln_flush(ptr-64);
        }
        used = total % 8;
        tail = joined;
    }
};
struct Limits{uint16_t value[Size/2]{};constexpr Limits(){for(unsigned i=0;i<Size/2;i++){unsigned x=2*i+1,m=Size;for(unsigned b=1;b<=K;b++){unsigned t=(x&((1u<<b)-1))<<(K-b);if(t<m)m=t;}value[i]=m;}}};static constexpr Limits limit27{};
struct Tables {
    alignas(64) unsigned char row[8][LSTRIDE];
    uint16_t low[MAXW], cut[Size];
    unsigned count, plen;
    void build(unsigned a) {
        count = 0;
        for(unsigned j=0;j<Size/2;j++){cut[2*j]=count;low[count]=2*j+1;count+=a<limit27.value[j];cut[2*j+1]=count;}
        unsigned pad = (-count)&7u;
        std::memmove(low+pad, low, count*sizeof(*low));
        for (unsigned i=0;i<pad;++i) low[i]=0;
        for(unsigned x=0;x<Size;++x) cut[x]=(uint16_t)(cut[x]+pad);
        count+=pad; plen=count;
        unsigned char *r0=row[0];
        r0[0]=0;
        {   uint64_t acc=0; unsigned nb=0; unsigned char *wp=r0+1;
            for(unsigned i=0;i<plen;i++){
                acc=(acc<<N)|low[i]; nb+=N;
                while(nb>=8){ nb-=8; *wp++=(unsigned char)((acc>>nb)&0xffu); }
            }
        }
        unsigned len = plen*N/8;
        for(unsigned q=1;q<8;q++){
            unsigned char *dst=row[q]; const unsigned char *src=r0;
            dst[0]=(unsigned char)(src[0]>>q);
            __m128i rc=_mm_cvtsi32_si128((int)q), ls=_mm_cvtsi32_si128((int)(8-q));
            __m256i lc=_mm256_set1_epi8((char)(255u>>q)), hc=_mm256_set1_epi8((char)(255u<<(8-q)));
            unsigned j=1;
            for(;j+32<=len+1;j+=32){
                __m256i at=_mm256_loadu_si256((const __m256i*)(src+j));
                __m256i bf=_mm256_loadu_si256((const __m256i*)(src+j-1));
                _mm256_storeu_si256((__m256i*)(dst+j), _mm256_or_si256(
                    _mm256_and_si256(_mm256_srl_epi16(at,rc),lc),
                    _mm256_and_si256(_mm256_sll_epi16(bf,ls),hc)));
            }
            for(;j<len+1;j++) dst[j]=(unsigned char)((src[j]>>q)|(src[j-1]<<(8-q)));
        }
    }
};
template<unsigned J> inline uint64_t lane(uint64_t w){
    constexpr unsigned offset=J*64%N;
    uint64_t r = w << (64-N+offset);
    if constexpr(2*N-offset<=64) r |= w << (64-2*N+offset);
    if constexpr(3*N-offset<=64) r |= w << (64-3*N+offset);
    if constexpr(4*N-offset<=64) r |= w << (64-4*N+offset);
    if constexpr((64+offset)%N!=0) r |= w >> (N-(64+offset)%N);
    return r;
}
inline uint64_t roll(uint64_t last, uint64_t curr,unsigned offset){
    return __builtin_bswap64(uint64_t((((unsigned __int128)last<<64)|curr)>>offset));
}
}
void debruijn(unsigned, char *output){
    static Tables tables;
    alignas(64) static unsigned char hb3[192];
    Writer writer{(unsigned char*)output,(unsigned char*)output+(uint64_t(1)<<(N-3))};
    unsigned h=0,period=1,prior=~0u;
    for(;;){
        unsigned a=h>>(M-K);
        if(a!=prior){tables.build(a);prior=a;}
        uint64_t base=uint64_t(h)<<K;
        unsigned bound;
        if(period>=K) bound=(h>>(period-K)) & Mask;
        else {
            uint64_t repeat=base;
            for(unsigned d=period;d<N;d*=2) repeat|=repeat>>d;
            bound=repeat & Mask;
        }
        if(N%period==0) writer.put(h>>(M-period),period);
        unsigned i=tables.cut[bound], length=tables.count;
        if(i<length){
            unsigned offset=writer.used;
            unsigned L=length-i;
            unsigned q=(offset - i*N)&7u;
            unsigned J=(8u + i*N + q - offset)>>3;
            unsigned bytes=(offset + L*N)>>3;
            unsigned mask=(0xffu<<(8-offset))&255u;
            unsigned carry=(unsigned)((writer.tail<<(8-offset))&mask);
            uint64_t w0=lane<0>(base),w1=lane<1>(base),w2=lane<2>(base),w3=lane<3>(base);
            __m256i high=_mm256_set_epi64x((long long)roll(w2,w3,offset),(long long)roll(w1,w2,offset),
                                           (long long)roll(w0,w1,offset),(long long)roll(0,w0,offset));
            _mm256_storeu_si256((__m256i*)hb3,high);
            _mm256_storeu_si256((__m256i*)(hb3+27),high);
            _mm256_storeu_si256((__m256i*)(hb3+54),high);
            _mm256_storeu_si256((__m256i*)(hb3+81),high);
            const unsigned char *Ls=tables.row[q]+J;
            auto get0=[&](unsigned pos,unsigned ph){return _mm256_or_si256(_mm256_loadu_si256((const __m256i*)(Ls+pos)),_mm256_loadu_si256((const __m256i*)(hb3+ph)));};
            unsigned char *op=writer.ptr;
            unsigned pb=(unsigned)((Ls[0]|hb3[0])&~mask)|carry;
            unsigned fill=(unsigned)((uintptr_t)op&63u);
            if(bytes){
              unsigned t=0;
              if(fill){
                unsigned need=64u-fill;
                __m256i v0=_mm256_insert_epi8(get0(0,0),pb,0);
                _mm256_storeu_si256((__m256i*)(LNBUF+fill),v0);
                if(fill<32&&bytes>32)_mm256_storeu_si256((__m256i*)(LNBUF+fill+32),get0(32,5));
                if(bytes>=need){ln_flush(op-fill);t=need;}
                else t=bytes;
              }
              if(t<bytes){
                unsigned pos=t,ph=pos%27u;
                if(!pos){
                  __m256i v0=_mm256_insert_epi8(get0(0,0),pb,0);
                  if(bytes>=64){_mm256_stream_si256((__m256i*)op,v0);_mm256_stream_si256((__m256i*)(op+32),get0(32,5));pos=64;ph=10;}
                  else {_mm256_storeu_si256((__m256i*)LNBUF,v0);if(bytes>32)_mm256_storeu_si256((__m256i*)(LNBUF+32),get0(32,5));pos=bytes;}
                }
                for(;pos+64<=bytes;pos+=64){
                  _mm256_stream_si256((__m256i*)(op+pos),get0(pos,ph));
                  _mm256_stream_si256((__m256i*)(op+pos+32),get0(pos+32,ph+5));
                  ph+=10;if(ph>=27)ph-=27;
                }
                if(pos<bytes){
                  unsigned r=bytes-pos;
                  _mm256_storeu_si256((__m256i*)LNBUF,get0(pos,ph));
                  if(r>32)_mm256_storeu_si256((__m256i*)(LNBUF+32),get0(pos+32,ph+5));
                }
              }
            }
 writer.ptr=op+bytes;
            writer.used=(offset+L*N)&7u;
            writer.tail=tables.low[length-1];
        }
        ++h;
        period=M-__builtin_ctz(h);
        if(!period) break;
        if(period*2>=M) h|=h>>period;
        else for(unsigned d=period;d<M;d*=2) h|=h>>d;
    }
unsigned _tf=(unsigned)((uintptr_t)writer.ptr&63u);if(_tf){unsigned char*_ln=writer.ptr-_tf;for(unsigned _i=0;_i<_tf;_i++)_ln[_i]=LNBUF[_i];}
_mm_sfence();}

CompilationN/AN/ACompile OKScore: N/A

Testcase #12.096 ms16 MB + 40 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-21 00:26:35 | Loaded in 30 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠