提交记录 162451


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_maker pagerank20. 测测你的网页排序-scale20 Accepted 100 688.353 ms 115576 KB C++17 11.19 KB
提交时间 评测时间
2026-11-17 01:02:53 2026-11-17 02:34:05
// Pure native PageRank reference. No generator, seed, input table, or answer data.
// Mathematical target: mean-normalized converged PageRank, damping0.85.
// Each released test must pass the separate offline1e-9 precision certification.
#include <immintrin.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstddef>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <immintrin.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#ifndef DUCK_PAGERANK_EDGE_DEFINED
#define DUCK_PAGERANK_EDGE_DEFINED
struct Edge {unsigned src,dst;};
#endif
namespace page {
static void*alloc(size_t s){void*p=nullptr;if(posix_memalign(&p,4096,s))abort();return p;}
struct Kahan{double s=0,c=0;void add(double x){double y=x-c,t=s+y;c=(t-s)-y;s=t;}};
static void permutation(unsigned n,const unsigned*degree,unsigned*perm);
// Incoming CSR: each input src->dst adds the column src to row dst.
// The first short write aligns each bucket; all subsequent full batches stream.
static void build(unsigned n,unsigned m,const Edge*a,unsigned*off,unsigned*col,unsigned*degree){
 constexpr unsigned bits=9,rows=512,mask=511;unsigned nb=(n+mask)>>bits;
 auto*count=(unsigned*)calloc(nb,4);auto*start=(unsigned*)malloc(((size_t)nb+1)*4);
 auto*cursor=(unsigned*)malloc((size_t)nb*4);auto*fill=(unsigned char*)calloc(nb,1);auto*target=(unsigned char*)malloc(nb);
 auto*fifo=(unsigned*)alloc((size_t)nb*32);if(!count||!start||!cursor||!fill||!target)abort();
 memset(degree,0,(size_t)n*4);auto*low=(unsigned char*)calloc(n,1);if(!low)abort();
 for(unsigned e=0;e<m;++e){++count[a[e].dst>>bits];if(++low[a[e].src]==0)++degree[a[e].src];}
 for(unsigned i=0;i<n;++i)degree[i]=(degree[i]<<8)|low[i];free(low);
 unsigned size=0;for(unsigned b=0;b<nb;++b){start[b]=cursor[b]=size;size+=count[b];target[b]=8-(cursor[b]&7);}start[nb]=size;
 for(unsigned e=0;e<m;++e){unsigned b=a[e].dst>>bits,j=fill[b];fifo[(size_t)b*8+j]=(a[e].src<<bits)|(a[e].dst&mask);++j;
  if(j==target[b]){auto*f=fifo+(size_t)b*8;auto*p=col+cursor[b];if(target[b]<8)memcpy(p,f,j*4);else _mm256_stream_si256((__m256i*)p,_mm256_load_si256((const __m256i*)f));cursor[b]+=j;fill[b]=0;target[b]=8;}else fill[b]=j;
 }
 _mm_sfence();for(unsigned b=0;b<nb;++b)memcpy(col+cursor[b],fifo+(size_t)b*8,fill[b]*4);
 for(unsigned b=0;b<nb;++b){unsigned histogram[rows]={},next[rows],end[rows];unsigned begin=start[b],stop=start[b+1],rowbase=b<<bits,rowcount=n-rowbase<rows?n-rowbase:rows;
  for(unsigned p=begin;p<stop;++p)++histogram[col[p]&mask];unsigned first=begin;
  for(unsigned r=0;r<rowcount;++r){off[rowbase+r]=next[r]=first;first+=histogram[r];end[r]=first;}
  for(unsigned r=0;r<rowcount;++r)while(next[r]<end[r]){unsigned p=next[r],key=col[p]&mask;if(key==r){++next[r];continue;}unsigned q=next[key]++,c=col[p];col[p]=col[q];col[q]=c;}
  for(unsigned p=begin;p<stop;++p)col[p]>>=bits;
 }
 off[n]=m;free(fifo);free(target);free(fill);free(cursor);free(start);free(count);
}
static unsigned bin(unsigned d){return d?32-__builtin_clz(d):0;}
static void permutation(unsigned n,const unsigned*degree,unsigned*perm){unsigned count[33]={},next[33];for(unsigned i=0;i<n;++i)++count[bin(degree[i])];unsigned first=0;for(unsigned b=33;b-->0;){next[b]=first;first+=count[b];}for(unsigned i=0;i<n;++i)perm[i]=next[bin(degree[i])]++;}
static double hsum(__m256d a){__m128d s=_mm_add_pd(_mm256_castpd256_pd128(a),_mm256_extractf128_pd(a,1));s=_mm_add_sd(s,_mm_unpackhi_pd(s,s));return _mm_cvtsd_f64(s);}
// Blocked positive summation bounds rounding at high-degree hubs.
static double row_sum(unsigned p,unsigned end,const unsigned*col,const double*q){Kahan total;
 while(p+256<=end){__m256d a=_mm256_setzero_pd();unsigned stop=p+256;for(;p<stop;p+=4){__m128i k=_mm_loadu_si128((const __m128i*)(col+p));a=_mm256_add_pd(a,_mm256_i32gather_pd(q,k,8));}total.add(hsum(a));}
 __m256d a=_mm256_setzero_pd();for(;p+4<=end;p+=4){__m128i k=_mm_loadu_si128((const __m128i*)(col+p));a=_mm256_add_pd(a,_mm256_i32gather_pd(q,k,8));}total.add(hsum(a));for(;p<end;++p)total.add(q[col[p]]);return total.s;}
struct Progress{double l1,max_delta,dangling,mass,zN,zD;};
static __attribute__((noinline,noclone)) Progress step(unsigned n,const unsigned*off,const unsigned*col,const unsigned*perm,const double*factor,const double*q,double*next,double*rank,double base){Kahan l1,dangling,mass,zN,zD;double mx=0;
 for(unsigned i=0;i<n;++i){double value=base+row_sum(off[i],off[i+1],col,q),signed_delta=value-rank[i],delta=fabs(signed_delta);rank[i]=value;next[perm[i]]=value*factor[i];l1.add(delta);mass.add(value);if(factor[i]==0){dangling.add(value);zD.add(signed_delta);}else zN.add(signed_delta);if(delta>mx)mx=delta;}
 return {l1.s,mx,dangling.s,mass.s,zN.s,zD.s};}
}

namespace page {
struct Rank2 {double a,b,c,d,det;};
static Rank2 prepare_rank2(unsigned n,unsigned non,const double*rank,double initialbase,const double*factor,double*h){
 Kahan hn,hd;for(unsigned i=0;i<n;++i){h[i]=non?(rank[i]-initialbase)/(.85*non):0;(factor[i]==0?hd:hn).add(h[i]);}
 double un=(double)non/n,ud=1-un;Rank2 q{1-.85*hn.s,-.85*un,-.85*hd.s,1-.85*ud,0};q.det=q.a*q.d-q.b*q.c;return q;
}
static double correct_rank2(unsigned n,const unsigned*perm,const double*factor,const double*h,const Rank2&c,const Progress&p,double*rank,double*next){
 double an=(c.d*p.zN-c.b*p.zD)/c.det,ad=(c.a*p.zD-c.c*p.zN)/c.det,uniform=.85*ad/n;Kahan dangling;
 for(unsigned i=0;i<n;++i){rank[i]+=.85*h[i]*an+uniform;next[perm[i]]=rank[i]*factor[i];if(factor[i]==0)dangling.add(rank[i]);}return dangling.s;
}
}

#define COMPACT_APPROX_H
#define COMPACT_DIRECT_SEED
// Requires pagerank_bytecount.hpp (page::build, row_sum, Kahan).
// Exact Schur elimination of dangling and zero-indegree source vertices.
namespace compact_pr {
struct Model {
 unsigned n,m,core=0,sources=0,active=0;
 unsigned *off,*col,*degree,*perm,*orig,*begin,*end,*index;
 double *factor,*g,*v,*rank,*qa,*qb;double vsum=0,denominator,totalRank=0;
#ifdef COMPACT_PROFILE
 uint64_t after_build=0,after_prep=0;
#endif
};
static Model build(unsigned n,unsigned m,const Edge*edges){
 Model z{};z.n=n;z.m=m;
 z.off=(unsigned*)page::alloc(((size_t)n+1)*4);z.col=(unsigned*)page::alloc((size_t)(m?m:1)*4);
 z.degree=(unsigned*)page::alloc((size_t)n*4);z.perm=(unsigned*)page::alloc((size_t)n*4);
 page::build(n,m,edges,z.off,z.col,z.degree);
#ifdef COMPACT_PROFILE
 _mm_lfence();z.after_build=__rdtsc();
#endif
 unsigned cc[33]={},ss[33]={},cp[33],sp[33];
 for(unsigned i=0;i<n;++i)if(z.degree[i]){unsigned b=page::bin(z.degree[i]);if(z.off[i]!=z.off[i+1]){++cc[b];++z.core;}else{++ss[b];++z.sources;}}
 z.active=z.core+z.sources;unsigned p=0;for(unsigned b=33;b-->0;){cp[b]=p;p+=cc[b];}for(unsigned b=33;b-->0;){sp[b]=p;p+=ss[b];}
 for(unsigned i=0;i<n;++i)z.perm[i]=z.degree[i]?(z.off[i]!=z.off[i+1]?cp[page::bin(z.degree[i])]++:sp[page::bin(z.degree[i])]++):~0u;
 const size_t cbytes=(size_t)(z.core?z.core:1)*8,abytes=(size_t)(z.active?z.active:1)*8;
 z.orig=(unsigned*)page::alloc(cbytes/2);z.begin=(unsigned*)page::alloc(cbytes/2);z.end=(unsigned*)page::alloc(cbytes/2);z.index=(unsigned*)page::alloc(cbytes/2);
 z.factor=(double*)page::alloc(abytes);z.g=(double*)page::alloc(cbytes);z.v=(double*)page::alloc(cbytes);z.rank=(double*)page::alloc(cbytes);z.qa=(double*)page::alloc(abytes);z.qb=(double*)page::alloc(abytes);
 for(unsigned i=0;i<n;++i)if(z.degree[i])z.factor[z.perm[i]]=.85/z.degree[i];
 // SIMD map is separate from source/core partition; sources preserve exact factors.
 unsigned mapped=0;for(;mapped+8<=m;mapped+=8){__m256i old=_mm256_load_si256((const __m256i*)(z.col+mapped));__m256i ix=_mm256_i32gather_epi32((const int*)z.perm,old,4);_mm256_store_si256((__m256i*)(z.col+mapped),ix);}for(;mapped<m;++mapped)z.col[mapped]=z.perm[z.col[mapped]];
 unsigned k=0;page::Kahan vs,loss;uint64_t core_edges=0;
 z.denominator=n+.85*z.sources;const double a=.85/z.denominator;
 for(unsigned i=0;i<n;++i){unsigned lo=z.off[i],hi=z.off[i+1];
  if(z.degree[i]&&lo!=hi){unsigned l=lo,r=hi;double h=0;page::Kahan source;
   while(l<r){unsigned ix=z.col[l];if(ix<z.core){++l;
#ifdef COMPACT_APPROX_H
    // Approximate shape uses the exact final prefix length, no per-edge FP count.
#else
    h+=z.factor[ix];
#endif
   }
    else{source.add(z.factor[ix]);--r;z.col[l]=z.col[r];z.col[r]=ix;}}
   z.orig[k]=i;z.begin[k]=lo;z.end[k]=r;z.index[k]=z.perm[i];z.g[k]=1+source.s;
#ifdef COMPACT_APPROX_H
   z.v[k]=r-lo;core_edges+=r-lo;
#else
   z.v[k]=h/z.core-a*z.g[k];vs.add(z.v[k]);
#endif
   z.rank[k]=1;z.qa[z.index[k]]=z.factor[z.index[k]];++k;
  }else{for(unsigned j=lo;j<hi;++j){unsigned ix=z.col[j];
#ifdef COMPACT_APPROX_H
   if(ix<z.core)loss.add(z.factor[ix]);
#endif
  }}
 }
#ifdef COMPACT_APPROX_H
 const double survival=z.core?.85-loss.s/z.core:0;
 for(unsigned j=0;j<z.core;++j){z.v[j]=(core_edges?survival*z.v[j]/core_edges:0)-a*z.g[j];vs.add(z.v[j]);}
#endif
 z.vsum=vs.s;z.totalRank=z.core;
#ifdef COMPACT_DIRECT_SEED
 page::Kahan gsum;for(unsigned j=0;j<z.core;++j)gsum.add(z.g[j]);const double base=z.n/z.denominator,coef=base*gsum.s/(1-z.vsum);
 page::Kahan rsum;for(unsigned j=0;j<z.core;++j){z.rank[j]=base*z.g[j]+coef*z.v[j];z.qa[z.index[j]]=z.rank[j]*z.factor[z.index[j]];rsum.add(z.rank[j]);}z.totalRank=rsum.s;
#endif
#ifdef COMPACT_PROFILE
 _mm_lfence();z.after_prep=__rdtsc();
#endif
 return z;
}
struct Progress {double max_delta,delta_sum,base;};
static Progress step(Model&z,const double*q){double base=(z.n-.85*z.totalRank)/z.denominator;page::Kahan changes;double mx=0;
 for(unsigned k=0;k<z.core;++k){double value=base*z.g[k]+page::row_sum(z.begin[k],z.end[k],z.col,q),d=value-z.rank[k];z.rank[k]=value;changes.add(d);mx=fmax(mx,fabs(d));}
 return {mx,changes.s,base};
}
static void correct(Model&z,const Progress&p,double*next){const double coefficient=p.delta_sum/(1-z.vsum);
 for(unsigned k=0;k<z.core;++k){z.rank[k]+=z.v[k]*coefficient;next[z.index[k]]=z.rank[k]*z.factor[z.index[k]];}
 z.totalRank+=p.delta_sum+coefficient*z.vsum;
}
static double finish(Model&z,double*out){page::Kahan sum;for(unsigned k=0;k<z.core;++k)sum.add(z.rank[k]);double base=(z.n-.85*sum.s)/z.denominator;
 for(unsigned i=0;i<z.n;++i)out[i]=base;
 for(unsigned k=0;k<z.core;++k)out[z.orig[k]]=z.rank[k];
 for(unsigned i=0;i<z.n;++i)if(z.degree[i])z.qa[z.perm[i]]=out[i]*z.factor[z.perm[i]];
 for(unsigned i=0;i<z.n;++i)if(!z.degree[i])out[i]=base+page::row_sum(z.off[i],z.off[i+1],z.col,z.qa);
 return base;
}
static void release(Model&z){free(z.qb);free(z.qa);free(z.rank);free(z.v);free(z.g);free(z.factor);free(z.index);free(z.end);free(z.begin);free(z.orig);free(z.perm);free(z.degree);free(z.col);free(z.off);}
}


// Fourteen preconditioned corrections are an implementation choice, not the task definition.
// The operator and source/dangling elimination use double throughout.
static compact_pr::Model pagerank_reference_model(unsigned n,unsigned m,const Edge*A){
 auto z=compact_pr::build(n,m,A);const double*q=z.qa;
 for(unsigned iteration=0;iteration<14&&z.core;++iteration){
  auto progress=compact_pr::step(z,q);
  double*next=(iteration&1)?z.qa:z.qb;compact_pr::correct(z,progress,next);q=next;
 }return z;
}
void pagerank(unsigned n,unsigned m,const Edge*A,double*out){
 auto z=pagerank_reference_model(n,m,A);compact_pr::finish(z,out);compact_pr::release(z);
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1688.353 ms112 MB + 888 KBAcceptedScore: 100


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