提交记录 168431


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex61s_agg5 1024. 测测你的划分 Accepted 100 65.727 ms 390640 KB C++17 5.02 KB
提交时间 评测时间
2026-11-17 14:32:42 2026-11-17 14:33:02
/* 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);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #165.727 ms381 MB + 496 KBAcceptedScore: 100


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