提交记录 179070
| 提交时间 |
评测时间 |
| 2026-11-19 09:29:01 |
2026-11-19 09:29:18 |
/* 引用 Stefan Edelkamp、Armin Weiß,BlockQuicksort: How Branch Mispredictions don't affect Quicksort,https://arxiv.org/abs/1604.06697 。参考缓存错误位置后成批交换的算法思想,自行实现固定阈值的 SIMD 索引打包;未复制论文或程序代码。 */
/* 本次实验:在左右各 128 项上用符号掩码收集需要交换的项,以整字节偏移打包八个位置。用单向游标消耗两边匹配的条目,收尾段独立原地划分。同时压缩原始数值以独立写回。 */
#include <immintrin.h>
#include <stdint.h>
#include <string.h>
#include <algorithm>
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3")
namespace {
constexpr unsigned B=128;
struct Masks{uint64_t slots[256]{};constexpr Masks(){
for(unsigned m=0;m<256;m++){unsigned j=0;for(unsigned i=0;i<8;i++)if((m>>i)&1){slots[m]|=uint64_t(i)<<(8*j);j++;}}
}};
alignas(64) static constexpr Masks masks{};
struct Side{alignas(64) unsigned char offset[B+8];unsigned v[B+8];unsigned at=0,end=0;};
template<bool right> inline void gather(Side&s,const unsigned*a){
s.at=s.end=0;
for(unsigned j=0;j<B;j+=8){auto v=_mm256_loadu_si256((const __m256i*)(a+j));
unsigned mask=_mm256_movemask_ps(_mm256_castsi256_ps(v))^(right?255:0);
uint64_t slots=masks.slots[mask],indices=slots+j*0x0101010101010101ull;
memcpy(s.offset+s.end,&indices,8);
auto order=_mm256_cvtepu8_epi32(_mm_cvtsi64_si128(slots));_mm256_storeu_si256((__m256i*)(s.v+s.end),_mm256_permutevar8x32_epi32(v,order));
s.end+=__builtin_popcount(mask);
}
}
}
void partition(unsigned n,unsigned*a){
unsigned lo=0,hi=n;Side L,R;
while(hi-lo>=2*B){
if(L.at==L.end)gather<false>(L,a+lo);
if(R.at==R.end)gather<true>(R,a+hi-B);
unsigned count=std::min(L.end-L.at,R.end-R.at);
for(unsigned j=0;j<count;j++){
unsigned h=R.at+j,l=L.at+j;
unsigned *x=a+lo+L.offset[l],*y=a+hi-B+R.offset[h];
*x=R.v[h];*y=L.v[l];
}
L.at+=count;R.at+=count;
if(L.at==L.end)lo+=B;
if(R.at==R.end)hi-=B;
}
while(lo<hi){
while(lo<hi&&!(a[lo]>>31))++lo;
while(lo<hi&&(a[hi-1]>>31))--hi;
if(lo<hi)std::swap(a[lo++],a[--hi]);
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 109.591 ms | 381 MB + 492 KB | Accepted | Score: 100 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2026-11-19 09:41:18 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠