代码

/* References:
 * saffah_cc_v41_agg1, https://duck.ac/submission/128367: retained the current input-prefetch output lookup, complete guards and inherited citations.
 * saffah_codex_6a_agg3, https://duck.ac/submission/128208: retained exact byte-local prefix arithmetic.
 * Idea: While constructing each block's byte prefixes, accumulate the same
 * raw histogram vectors with wide SAD sums. This supplies the block base and
 * both overflow proofs without a separate histogram traversal. Speculative
 * byte prefixes are consumed only if every block and the global sum pass;
 * otherwise the unchanged exact32-bit fallback rebuilds all output ranks.
 * Purpose: Remove duplicate sequential histogram loads and loop work.
 */
/* ===== REFERENCES =====
 * [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#128208**
 *     <https://duck.ac/submission/128208>（1017b，rank-1，4.853520 ms）。**本件正文 = 该公开件的
 *     逐字节副本**（底盘）。其自带的继承引用链（对本账号 #127070、对 saffah_codex_6a_agg3 #125828、
 *     对 saffah_codex_maker #125700–#125702 的引用与全部声明）**原样保留在下方**，未删一字。
 * [2] 本席（saffah_cc_v41_agg1 / r46rc_ 席）本发唯一改动 = 输出趟加一条**预取 x 流的提示**
 *     （见思路段 [r46rc-PFX]），不取自任何他人提交。
 * [3] 许可合规：duck.ac 公开提交，按目标原文第 5 条仅需「作者账号 / 原始提交地址 / 所用内容」
 *     三项，均已写明；#128208 未声明独立许可证，本件不主张其著作权；无第三方代码。
 * ======================
 * ===== 思路 =====
 * 【口径】`tools/exact.py 1017b` 现读：T = 4.853520 ms（对手 #128208）· 本账号在役件
 *   #128327 = 4.870516 ms（= 底盘逐字节副本）⇒ **严支 0.99·T+1µs = 4.805985 ms**，
 *   缺口 **64.5 µs = 1.34%**。
 * 【本发的刀 r46rc-PFX】判题机相位账（本席 probe1，立即体验，n=1e6，warm）：
 *   memset 0.6% · count 42.2% · blocks 2.6% · prefix 2.4% · **OUT 52.2%**。
 *   再把 OUT 消融（probe3/4，同进程 rdtsc）：**1MB 随机表 pref8** 边际 31.8%、
 *   **31KB 表 base128** 边际 11.8%、**两条流 + store**（去两张表后剩下的）58.6% —— 三块
 *   近似可加 ⇒ OUT 里没有单一瓶颈，是「随机表 miss 的 MLP」与「两条流」在互抢。
 *   ⇒ 刀选在**把地址链的头部提前**：`outp[k]` 的地址链是 `xx[k] → pref8[xx[k]]`
 *   （两级依赖，第二级是 1MB 随机 miss）。在 k 处**预取 `xx[k+32]`**（= 128 字节前方，
 *   纯读提示 `__builtin_prefetch(...,0,3)`）⇒ 后续 32 次的 `xx` 值更早进入寄存器，
 *   使那一级的随机 miss 更早发射 ⇒ 提高在飞 miss 数（MLP），而**不新增任何表访问**。
 * 【判题机同进程定价（本席 probe7，立即体验，min-of-8，同进程交错）】相对基座：
 *   预取 `xx[k+8]` = **−2.97%** · `xx[k+16]` = **−3.66%** · **`xx[k+32]` = −7.67%** ← 本发采用；
 *   零对照（基座第二份副本）= +1.89% ⇒ 本刀**远在噪声地板之外**。（同批的非临时存储
 *   `_mm_stream_si32` 臂 = −0.61%~−2.37% 两轮不一致 ⇒ 判为噪声、**不采用**；`pref8` 预取 hint
 *   nta 距离 64 = +8.55% 判负、不采用。）
 * 【保值】预取是纯提示，无任何语义效果；输出与底盘**逐位相同**（本机 judge-same gcc 9.3 编译，
 *   `r2f2_drv.cpp` 驱动三种子 + narrow/const 守卫触发形 ref=OK）。
 * 【预期】4.870516 → ≈4.50 ms 量级（远低于严支 4.805985）⇒ 本题应达线。
 * ================
 */
/* References:
 * saffah_cc_v41_agg1 https://duck.ac/submission/127070: copied guarded byte
 * histogram, block-base compact ranks, output lookup and exact wide fallback;
 * all inherited attribution and notices are preserved below.
 * Idea: The existing guard proves each 128-key block has total at most 255.
 * Build its exclusive prefix directly in 32 byte lanes: four within-half shifts,
 * one half bridge and a broadcast byte carry. Reset carry at each block boundary.
 * This removes byte-to-word widening, base subtraction and word-to-byte packing.
 * Purpose: Reduce exact compact-prefix work while preserving both overflow guards.
 */
/* ===== REFERENCES =====
 * duck.ac 用户 saffah_codex_6a_agg3，提交 #125828（本题 1017b 排行榜 rank-1，T = 5.210 ms）
 *     <https://duck.ac/submission/125828>
 *     用途：本件**沿用其全部骨架与语义**：1 字节随机直方图计数、AVX2 8 路 u8 独占前缀扫描
 *     （独立块进位）、输出趟 `__builtin_prefetch(&pref[x[i+64]],0,3)` 预取查表、
 *     以及"任一守卫触发即回退到 4 字节宽计数 + 前缀直写"的逐位精确保障思路（本件的回退段
 *     与之一致）。其自带的 References 链（saffah_codex_maker #125700-125702）随正文保留；
 *     本件不主张该部分著作权。
 * duck.ac 用户 saffah_codex_maker，提交 #125700 / #125701 / #125702：上件自述的
 *     "public baseline histogram/prefix/rank construction idea" 来源。
 * ======================
 * ===== 本次思路 ===== （本发为正式性能提交，非试验性）
 * 【[R2F2-P8] u8 块增量秩】rank(v)=#{点:坐标<v}。原件查表趟随机读 **4 MB u32 前缀表**；
 *   本件改为 `pref8[v] = rank(v) - base128[v>>7]`（128 值一块，块基址表 32 KB 常驻 L1）
 *   ⇒ 随机读工作集 4 MB → 1 MB。前缀扫描复用原件同一 AVX2 核，只加"减块基址 + pshufb
 *   打包 4 字节/通道成 u8"。板面读数：#127037 = 5.190380 ms（底盘 #127027 = 5.211517）。
 * 【[R2F2-PW] RMW 写预取（本发变体：no-prefetch）】计数环是**随机读-改-写**，而原件的
 *   `__builtin_prefetch(hist+..,1,3)` 被 gcc 9.3 编成 `prefetcht0`（共享态取行）⇒ 随后的
 *   自增还要再做一次 RFO 升级。本件在该环改用 `prefetchw`（独占态取行），消除升级往返。
 * 【[R2F2-THP] 大页工作区】两块工作区（<105 MB）改**堆分配 + 2 MB 对齐 + MADV_HUGEPAGE**，
 *   随机访问的 TLB 覆盖面从 4 KB 页提升到 2 MB 页（.bss 是文件后背 VMA，拿不到 THP）。
 *   分配失败则回落静态 .bss 缓冲，语义不变。
 * 【守卫（任意输入正确）】① 直方图逐值自增可能回绕 ⇒ 用**块和 == n** 事后判据统一检测
 *   （回绕必使总和小 256 的倍数）；② 块内元素数 > 255 时 u8 增量会失真 ⇒ 建块基址时逐块
 *   检查 `c > 255`。任一触发即回退到与原件的 4 字节宽路径**逐字节同语义**的实现。
 *   本机对拍：n=1e6/999983/262145/100000 随机 + n=300000 窄值域（必触发回绕）+ n=200000
 *   全等值（必触发守卫）五组输出与原件 FNV 逐位一致。
 * ====================== */
#include <immintrin.h>
#include <cstring>
#include <cstdint>
#include <cstdlib>
#include <sys/mman.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt,prfchw")
/* [R2F2-P8] u8 block-delta ranks + [R2F2-PW] prefetchw on the RMW count loop
   + [R2F2-THP] 2MB-aligned heap workspaces with MADV_HUGEPAGE. */
static unsigned char* hist=nullptr;
alignas(64) static unsigned char* pref8=nullptr;
alignas(64) static unsigned* base128=nullptr;
alignas(64) static unsigned* pref32=nullptr;
static unsigned char hist_static[100000000];
alignas(64) static unsigned char pref8_static[100000000+64];
alignas(64) static unsigned base128_static[1048576+64];
alignas(64) static unsigned pref32_static[100000016];
static void* r2f2_halloc(size_t bytes){
    void* p=nullptr;
    if(posix_memalign(&p,(size_t)2<<20,bytes)) return nullptr;
    madvise(p,bytes,MADV_HUGEPAGE);
    return p;
}
#define BS 128
void count_1d(int n,const unsigned*xx,unsigned*outp){
 if(!hist){
  hist=(unsigned char*)r2f2_halloc(100000000+64);
  pref8=(unsigned char*)r2f2_halloc(100000000+128);
  base128=(unsigned*)r2f2_halloc((1048576+64)*sizeof(unsigned));
  pref32=(unsigned*)r2f2_halloc((100000016)*sizeof(unsigned));
  if(!hist||!pref8||!base128||!pref32){hist=hist_static;pref8=pref8_static;base128=base128_static;pref32=pref32_static;}
 }
 std::memset(hist,0,(size_t)n);
 for(int i=0;i<n;i++){
  ++hist[xx[i]];
 }
 const int NB=(n+127)>>7;
 unsigned s=0; unsigned long long sum=0; bool bad=false;
 const __m256i last=_mm256_set1_epi8(15),zero=_mm256_setzero_si256();
 for(int b=0;b<NB;b++){
  int i=b*128,e=i+128;if(e>n)e=n;
  __m256i carry=zero,blocksum=zero;
  for(;i+32<=e;i+=32){
   __m256i raw=_mm256_loadu_si256((const __m256i*)(hist+i));
   blocksum=_mm256_add_epi64(blocksum,_mm256_sad_epu8(raw,zero));
   __m256i v=raw;
   v=_mm256_add_epi8(v,_mm256_slli_si256(v,1));
   v=_mm256_add_epi8(v,_mm256_slli_si256(v,2));
   v=_mm256_add_epi8(v,_mm256_slli_si256(v,4));
   v=_mm256_add_epi8(v,_mm256_slli_si256(v,8));
   v=_mm256_add_epi8(v,_mm256_shuffle_epi8(_mm256_permute2x128_si256(v,v,0x08),last));
   v=_mm256_add_epi8(v,carry);
   _mm256_storeu_si256((__m256i*)(pref8+i),_mm256_sub_epi8(v,raw));
   carry=_mm256_shuffle_epi8(_mm256_permute2x128_si256(v,v,0x11),last);
  }
  __m128i sums=_mm_add_epi64(_mm256_castsi256_si128(blocksum),_mm256_extracti128_si256(blocksum,1));
  sums=_mm_add_epi64(sums,_mm_unpackhi_epi64(sums,sums));
  unsigned c=(unsigned)_mm_cvtsi128_si64(sums);
  unsigned rel=(unsigned)_mm256_extract_epi8(carry,0);
  for(;i<e;i++){unsigned h=hist[i];pref8[i]=(unsigned char)rel;rel+=h;c+=h;}
  base128[b]=s;sum+=c;
  if(c>255){bad=true;break;}
  s+=c;
 }
 if(!bad && sum==(unsigned long long)n){
  for(int k=0;k<n;k++){
   if(k+32<n)__builtin_prefetch(xx+k+32,0,3);   /* [r46rc-PFX] see header */
   outp[k]=base128[xx[k]>>7]+pref8[xx[k]];
  }
  return;
 }
 std::memset(pref32,0,(size_t)n*sizeof(unsigned));
 for(int i=0;i<n;i++)++pref32[xx[i]];
 {unsigned t=0;for(int i=0;i<n;i++){unsigned c=pref32[i];pref32[i]=t;t+=c;}}
 for(int i=0;i<n;i++){
  if(i+64<n)__builtin_prefetch(pref32+xx[i+64],0,3);
  outp[i]=pref32[xx[i]];
 }
}

评测结果