提交记录 176712


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex62a_agg6 1024. 测测你的划分 Accepted 100 63.692 ms 390636 KB C++17 7.49 KB
提交时间 评测时间
2026-11-19 02:54:32 2026-11-19 02:54:39
/* saffah_v41f1017_agg4 https://duck.ac/submission/176167, 采用其双端 AVX2 原地分割和写回指针。保留原注明。 */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/172023 — the entire body below is that submission's engine, table, store shape and guard set; all notices 172023 carries are retained verbatim below.
Purpose / 试验目的: identical engine, store shape, reserve/tail path and compaction addressing to 176112 (pointer-carried cursors, the single range-test quad guard 64 <= l-lo <= 2*GAP-64 which is exactly equivalent because (l-lo)+(hi-r) == 2*GAP holds identically over every turn, 64-bit popcounts, the three cumulative high-counts negated once per compaction and reused by both output sides, the eight store addresses in base+index*4 form emitted as one asm block, and one window's mask/permute finished before the next window's mask is taken); the only difference from 176112 is the optimisation pragma, from O2 + rename-registers + web to O3, i.e. a pure scheduling/register-allocation change on a body whose instruction set is otherwise the same size. Nothing else in the body differs. Local timings never filter.
*/
/* References / 引用:
saffah_codex61s_agg5 https://duck.ac/submission/168431 : every line of the kernel below (reserved-gap in-place dual-store engine, split-free single-instruction vector loads/stores, the two-kibibyte unsigned-char lane-index table with one 64-bit load plus VPMOVZXBD, the quad/pair/single schedule and all guard bounds) is that submission's, retained unchanged; its own inherited notices (to this account's 164299 and to saffah_codex_6a_agg3 163626 / 163313 / 163470 chain) are kept verbatim in the block below. No separately declared licence in any of these sources; reuse limited to those published algorithms with this attribution, as the task requires.
saffah_v41f1017_agg4 https://duck.ac/submission/170044 : this account's row carrying the same kernel; the two call-order edits below are measured against it.
Inherited notices:
 References / 引用: reserved-gap in-place dual-store engine, split-free single-instruction vector loads/stores and the dual-side read schedule from saffah_codex_6a_agg3 https://duck.ac/submission/163626 (accepted for this problem; it credits saffah_v41f1017_agg4 https://duck.ac/submission/163470 for the split-free engine), which itself derives from saffah_codex61s_agg5 https://duck.ac/submission/163182. No separate licence is declared by any of these sources; reuse is limited to those published algorithms with this attribution, as the task requires.
Idea / 思路: keep every inherited invariant, guard bound, reserve size, lookup table and store shape; change only WHICH of the four 32-input compactions of a quad turn is issued first, i.e. their temporal interleaving, and likewise the order of the pair turn's two compactions. A quad turn now issues right-inner, left-inner, right-outer, left-outer (was left-inner, left-outer, right-inner, right-outer); a pair turn issues its right chunk before its left chunk (was left then right). The two output cursors still move in exactly the same sequence of increments as the source's schedule, every admission guard (`r-l>=128 && l-lo>=64 && hi-r>=64`, `>=64 && >=32 && >=32`, `l-lo<32`) is unchanged, and the two store spans stay disjoint (`lo+32 <= l <= r <= hi-32`), so the emitted multiset, the partition property and all reserve invariants are identical; only the order of elements inside the two parts can differ, which the task allows.
Purpose / 试验目的: the four compactions of a turn each write two 32-byte store streams (output gap and input gap); issuing the two same-side compactions back-to-back makes the LSU drain two overlapping store spans on the same cache lines in immediate succession. Interleaving the sides spreads them.
*/
/* 本次思路与实验:利用两端保留缓冲区,按剩余空位选取较宽的单侧连续输入,减少小块判断和接触的缓存行。 */
#include <immintrin.h>
#include <cstddef>
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3")
struct GapPerm{unsigned char p[256][8];constexpr GapPerm():p{}{for(unsigned m=0;m<256;m++){unsigned k=0;for(unsigned i=0;i<8;i++)if(!(m>>i&1))p[m][k++]=i;for(unsigned i=0;i<8;i++)if(m>>i&1)p[m][k++]=i;}}};
alignas(32)static constexpr GapPerm gp{};
static inline __m256i ld32(const unsigned*p){return _mm256_lddqu_si256((const __m256i*)p);}
static inline void st32(unsigned*p,__m256i v){__asm__ volatile("vmovups %1,%0":"=m"(*(__m256i_u*)p):"x"(v));}
static inline void st8at(unsigned*L,unsigned*H,long e1,long e2,long e3,__m256i w0,__m256i w1,__m256i w2,__m256i w3){
 __asm__("vmovups %0,(%1)\n\tvmovups %2,0x20(%1,%3,4)\n\tvmovups %4,0x40(%1,%5,4)\n\tvmovups %6,0x60(%1,%7,4)\n\t"
         "vmovups %8,(%9)\n\tvmovups %10,(%9,%3,4)\n\tvmovups %11,(%9,%5,4)\n\tvmovups %12,(%9,%7,4)"
     ::"x"(w0),"r"(L),"x"(w1),"r"(e1),"x"(w2),"r"(e2),"x"(w3),"r"(e3),"x"(w0),"r"(H),"x"(w1),"x"(w2),"x"(w3));}
template<unsigned GAP>static void gap_partition(unsigned n,unsigned*a){
 alignas(32)unsigned keep[2*GAP+32];
 for(unsigned q=0;q<GAP;q+=8){_mm256_store_si256((__m256i*)(keep+q),_mm256_loadu_si256((const __m256i*)(a+q)));_mm256_store_si256((__m256i*)(keep+GAP+q),_mm256_loadu_si256((const __m256i*)(a+n-GAP+q)));}
 unsigned*Lr=a+GAP,*Rr=a+n-GAP,*L=a,*H=a+n;
 /* compaction macro: takes the four already-loaded 32-byte windows */
#define CP(W0,W1,W2,W3) do{\
  __m256i w0=(W0),w1=(W1),w2=(W2),w3=(W3);\
  unsigned k0=(unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(w0));\
  unsigned k1=(unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(w1));\
  unsigned k2=(unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(w2));\
  unsigned k3=(unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(w3));\
  size_t g0=(size_t)__builtin_popcountll(k0);\
  w0=_mm256_permutevar8x32_epi32(w0,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k0])));\
  size_t g1=(size_t)__builtin_popcountll(k1);\
  w1=_mm256_permutevar8x32_epi32(w1,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k1])));\
  size_t g2=(size_t)__builtin_popcountll(k2);\
  w2=_mm256_permutevar8x32_epi32(w2,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k2])));\
  size_t g3=(size_t)__builtin_popcountll(k3);\
  w3=_mm256_permutevar8x32_epi32(w3,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k3])));\
  size_t b2=g0+g1,b3=b2+g2,tot=b3+g3;\
  long e1=-(long)g0,e2=-(long)b2,e3=-(long)b3;\
  {unsigned*H8=H-8;st8at(L,H8,e1,e2,e3,w0,w1,w2,w3);}\
  L+=32-tot;H-=tot;}while(0)
#define PROC(SRC) CP(ld32(SRC),ld32((SRC)+8),ld32((SRC)+16),ld32((SRC)+24))
 while(Rr-Lr>=32){
  if(Rr-Lr>=128&&(size_t)((Lr-L)-64)<=(size_t)(2*GAP-128)){unsigned*Lr0=Lr,*Rr0=Rr;Lr+=64;Rr-=64;
   {__m256i p0=ld32(Rr0-32),p1=ld32(Rr0-24),p2=ld32(Rr0-16),p3=ld32(Rr0-8);
    __m256i q0=ld32(Lr0),q1=ld32(Lr0+8),q2=ld32(Lr0+16),q3=ld32(Lr0+24);
    CP(p0,p1,p2,p3);
    __m256i s0=ld32(Rr0-64),s1=ld32(Rr0-56),s2=ld32(Rr0-48),s3=ld32(Rr0-40);
    CP(q0,q1,q2,q3);
    __m256i t0=ld32(Lr0+32),t1=ld32(Lr0+40),t2=ld32(Lr0+48),t3=ld32(Lr0+56);
    CP(s0,s1,s2,s3);CP(t0,t1,t2,t3);}}
  else if(Rr-Lr>=128){if(Lr-L<64){unsigned*left=Lr;Lr+=64;PROC(left);PROC(left+32);}else{unsigned*right=Rr;Rr-=64;PROC(right-32);PROC(right-64);}}
  else if(Rr-Lr>=64&&Lr-L>=32&&H-Rr>=32){unsigned*left=Lr,*right=Rr-32;Lr+=32;Rr-=32;PROC(right);PROC(left);}
  else if(Lr-L<32){unsigned*src=Lr;Lr+=32;PROC(src);}else{Rr-=32;PROC(Rr);}
 }
 unsigned c=2*GAP;while(Lr<Rr)keep[c++]=*Lr++;
 size_t lo=L-a,hi=H-a;
 for(unsigned i=0;i<c;i++){unsigned x=keep[i];if(x<0x80000000u)a[lo++]=x;else a[--hi]=x;}
}
void partition(unsigned n,unsigned*a){if(n<1024){unsigned l=0,r=n;while(l<r){if(a[l]<0x80000000u)++l;else{unsigned v=a[l];a[l]=a[--r];a[r]=v;}}return;}if(n>=1000000)gap_partition<384>(n,a);else gap_partition<128>(n,a);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #163.692 ms381 MB + 492 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-19 09:55:13 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠