代码

#define STAT 34
/* wc2017b2 sharing-structure probe: multiplicity statistics. */
static char pad[16 << 20];
static inline void dumpv(unsigned long long v){ if(v>7000)v=7000; volatile char*p=pad; for(unsigned long long i=0;i<v;i++)p[i*4096]=1; }
#ifndef STAT
#define STAT 0
#endif
static int cxs[300001], cys[300001];
static unsigned long long hk[1<<20]; static int hv[1<<20];
static int hget(unsigned long long key,int add){
    unsigned h=(unsigned)((key*0x9E3779B97F4A7C15ull)>>44)&((1<<20)-1);
    for(int t=0;t<12;t++){unsigned i=(h+t)&((1<<20)-1);
        if(hv[i]==0){ if(add){hk[i]=key;hv[i]=1;} return 0; }
        if(hk[i]==key){ if(add)hv[i]++; return hv[i]-1; } }
    return 0;
}
void solve(int n,int q,char*s1,char*s2,int*q_x,int*q_y,int*q_len,unsigned*ans){
    unsigned long long v=0; long long s=0; int c=0;
    (void)s1;(void)s2;
#if STAT==30   /* sum over queries of 1/k_x, /50 */
    { for(int i=0;i<n;i++)cxs[i]=0; for(int i=0;i<q;i++)if(q_x[i]<n)cxs[q_x[i]]++;
      double acc=0; for(int i=0;i<q;i++)if(q_x[i]<n)acc+=1.0/cxs[q_x[i]]; v=(unsigned long long)(acc/50); }
#elif STAT==31 /* sum 1/k_y /50 */
    { for(int i=0;i<n;i++)cys[i]=0; for(int i=0;i<q;i++)if(q_y[i]<n)cys[q_y[i]]++;
      double acc=0; for(int i=0;i<q;i++)if(q_y[i]<n)acc+=1.0/cys[q_y[i]]; v=(unsigned long long)(acc/50); }
#elif STAT==32 /* max multiplicity of x */
    { for(int i=0;i<n;i++)cxs[i]=0; for(int i=0;i<q;i++)if(q_x[i]<n)cxs[q_x[i]]++;
      int mx=0; for(int i=0;i<n;i++)if(cxs[i]>mx)mx=cxs[i]; v=mx; }
#elif STAT==33 /* #queries with k_x>=4, /50 */
    { for(int i=0;i<n;i++)cxs[i]=0; for(int i=0;i<q;i++)if(q_x[i]<n)cxs[q_x[i]]++;
      for(int i=0;i<q;i++)if(q_x[i]<n&&cxs[q_x[i]]>=4)c++; v=c/50; }
#elif STAT==34 /* sum 1/k_xy /50 (64-bit key hash) */
    { for(int i=0;i<(1<<20);i++)hv[i]=0;
      for(int i=0;i<q;i++)hget((unsigned long long)q_x[i]*1000003ull+(unsigned)q_y[i],1);
      double acc=0;
      for(int i=0;i<q;i++){int k=hget((unsigned long long)q_x[i]*1000003ull+(unsigned)q_y[i],0); acc+=1.0/(k?k:1);} 
      v=(unsigned long long)(acc/50); }
#elif STAT==35 /* #distinct x with k>=4, /10 */
    { for(int i=0;i<n;i++)cxs[i]=0; for(int i=0;i<q;i++)if(q_x[i]<n)cxs[q_x[i]]++;
      for(int i=0;i<n;i++)if(cxs[i]>=4)c++; v=c/10; }
#elif STAT==36 /* adjacent equal x count /10 */
    { for(int i=0;i+1<q;i++)if(q_x[i]==q_x[i+1])c++; v=c/10; }
#elif STAT==37 /* max multiplicity of (x,y) */
    { for(int i=0;i<(1<<20);i++)hv[i]=0; int mx=0;
      for(int i=0;i<q;i++){int k=hget((unsigned long long)q_x[i]*1000003ull+(unsigned)q_y[i],1)+1; if(k>mx)mx=k;} v=mx; }
#elif STAT==38 /* sum over queries of 1/k_x * (l/64) / 5000: effective shared-load work */
    { for(int i=0;i<n;i++)cxs[i]=0; for(int i=0;i<q;i++)if(q_x[i]<n)cxs[q_x[i]]++;
      double acc=0; for(int i=0;i<q;i++)if(q_x[i]<n)acc+=(double)(q_len[i]>>6)/cxs[q_x[i]]; v=(unsigned long long)(acc/5000); }
#elif STAT==39 /* sum(l)/1e7 control */
    { for(int i=0;i<q;i++)s+=(unsigned)q_len[i]; v=(unsigned long long)(s/10000000); }
#elif STAT==40 /* count l == n - max(x,y): /50 */
    { for(int i=0;i<q;i++){int m=q_x[i]>q_y[i]?q_x[i]:q_y[i]; if(q_len[i]==n-m)c++;} v=c/50; }
#elif STAT==41 /* #distinct x /50 */
    { for(int i=0;i<n;i++)cxs[i]=0; for(int i=0;i<q;i++)if(q_x[i]<n)cxs[q_x[i]]++;
      for(int i=0;i<n;i++)if(cxs[i])c++; v=c/50; }
#elif STAT==42 /* #distinct (x,y) /50 */
    { for(int i=0;i<(1<<20);i++)hv[i]=0; for(int i=0;i<q;i++)c+=hget((unsigned long long)q_x[i]*1000003ull+(unsigned)q_y[i],1)==0; v=c/50; }
#endif
    dumpv(300+v);
    for(int i=0;i<q;i++)ans[i]=0;
}

//TOKSTAT34Z

评测结果