Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
24535 yuanjiabao 【BJ】T1 C++ 运行超时 20 1000 MS 55308 KB 2071 2024-01-02 14:51:29

Tests(2/10):


#include<iostream> #include<cmath> #include<complex> using namespace std; using comp=complex<double>; const int N=1<<20,B=30; const double eps=1e-5; inline int extend(int x){while(x!=(x&-x))x+=x&-x;return x;} void convolution(comp F[],comp G[],comp H[],int n,comp c){ if(n==1){H[0]=F[0]*G[0];return;} comp rtc=sqrt(c); int mid=(n>>1); for(int i=0;i<mid;i++){ comp L=F[i],R=F[i+mid]; F[i]=L+R*rtc,F[i+mid]=L-R*rtc; L=G[i],R=G[i+mid]; G[i]=L+R*rtc,G[i+mid]=L-R*rtc; } convolution(F,G,H,mid,rtc); convolution(F+mid,G+mid,H+mid,mid,-rtc); for(int i=0;i<mid;i++){ comp L=H[i],R=H[i+mid]; H[i]=(L+R)/2.,H[i+mid]=(L-R)/2./rtc; } } comp F[N],G[N],H[N]; inline int read(){ int i=getchar(),r=0; while(i<'0'||i>'9')i=getchar(); while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r; } int cnt[N]; int n,m; int ans[N]; int stk[N],top; void init(){ cin>>n>>m; for(int i=1;i<=n;i++)cnt[read()]++; for(int i=1;i<=m;i++)if(cnt[i]>B)stk[++top]=i; } int main(){ // freopen("read.in","r",stdin); init(); for(int i=1;i<=top;i++){ for(int j=1;j<=top;j++)ans[stk[i]+stk[j]]+=min(cnt[stk[i]],cnt[stk[j]]); } int len=extend(m*2+1); for(int x=1;x<=B;x++){ for(int j=1;j<=m;j++){ if(cnt[j]==x)F[j]=cnt[j]; else F[j]=0; if(x<=cnt[j])G[j]=1; else G[j]=0; } F[0]=G[0]=0; for(int j=m+1;j<N;j++)F[j]=0,G[j]=0; convolution(F,G,H,len,1); for(int i=1;i<=m;i++)ans[i]+=(int)(H[i].real()+eps); for(int j=1;j<=m;j++){ if(cnt[j]==x)F[j]=1; else F[j]=0; if(x>cnt[j])G[j]=cnt[j]; else G[j]=0; } F[0]=G[0]=0; for(int j=m+1;j<N;j++)F[j]=0,G[j]=0; convolution(F,G,H,len,1); for(int i=1;i<=m;i++)ans[i]+=(int)(H[i].real()+eps); } for(int i=1;i<=m;i++)cout<<ans[i]/2<<' '; return 0; }


测评信息: