/* References / 引用:
saffah_v41f1017_agg4 https://duck.ac/submission/164299: complete four-chunk protected-gap compaction, exact original permutation entries, split-free input/stores and all inherited account/source/use notices retained here. No separately declared license. No other outside code.
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 and the two-hundred-and-fifty-six-plus reserve, and add one schedule step: when both output gaps have sixty-four free entries and two full sixty-four-input windows remain, consume two thirty-two-input chunks from the left and two from the right in one turn (four compactions), otherwise fall back to the inherited dual-side pair or single-side chunk. The same gap bound that protects the pair schedule protects the quad: the left store span ends at lo+128-prefix15 <= l+64 and the right span starts at hi-8-prefix15 >= r-64, both implied by gaps >= 64.
Purpose / 试验目的: halve the side-selection frequency once more without widening the register footprint, then re-validate the exact multiset, the partition property and every guard case at this fixed n.
Approach / 思路: Store each of the eight permutation indices as an unsigned byte, since every value is0..7. The complete256mask table shrinks8192→2048bytes. One64bit load plus VPMOVZXBD reconstructs the exact original eight32bit lane indices before VPERMD. Preserve every source-window admission, full-vector dual store, output cursor, reserve size and scalar fallback. This changes lookup storage/decoding while the partition invariant and input coverage remain identical.
Experiment purpose / 试验目的: GCC9 exhaustive65536sign layouts,4096sizes,8adversarial distributions,guards and complete100000000shape multiset/partition proof, then prompt official. Local timings never filter.
*/
#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__("vmovups %0,%1"::"x"(v),"m"(*(__m256i*)p));}
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)));}
size_t l=GAP,r=n-GAP,lo=0,hi=n;
auto process=[&](size_t src){
__m256i w0=ld32(a+src),w1=ld32(a+src+8),w2=ld32(a+src+16),w3=ld32(a+src+24);
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));
unsigned g0=(unsigned)__builtin_popcount(k0),g1=(unsigned)__builtin_popcount(k1);
unsigned g2=(unsigned)__builtin_popcount(k2),g3=(unsigned)__builtin_popcount(k3);
unsigned b1=g0,b2=g0+g1,b3=b2+g2,tot=b3+g3;
w0=_mm256_permutevar8x32_epi32(w0,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k0])));
w1=_mm256_permutevar8x32_epi32(w1,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k1])));
w2=_mm256_permutevar8x32_epi32(w2,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k2])));
w3=_mm256_permutevar8x32_epi32(w3,_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)gp.p[k3])));
st32(a+lo,w0);
st32(a+lo+8-b1,w1);
st32(a+lo+16-b2,w2);
st32(a+lo+24-b3,w3);
st32(a+hi-8,w0);
st32(a+hi-8-b1,w1);
st32(a+hi-8-b2,w2);
st32(a+hi-8-b3,w3);
lo+=32-tot;hi-=tot;
};
while(r-l>=32){
if(r-l>=128&&l-lo>=64&&hi-r>=64){size_t l0=l,r0=r;l+=64;r-=64;process(l0);process(l0+32);process(r0-32);process(r0-64);}
else if(r-l>=64&&l-lo>=32&&hi-r>=32){size_t left=l,right=r-32;l+=32;r-=32;process(left);process(right);}
else if(l-lo<32){size_t src=l;l+=32;process(src);}else{r-=32;process(r);}
}
unsigned c=2*GAP;while(l<r)keep[c++]=a[l++];
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<512>(n,a);else gap_partition<128>(n,a);}