QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#38316#1176. BinomialwyhaoWA 944ms99316kbC++641b2022-07-05 10:31:042022-07-05 10:31:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-05 10:31:06]
  • 评测
  • 测评结果:WA
  • 用时:944ms
  • 内存:99316kb
  • [2022-07-05 10:31:04]
  • 提交

answer

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
typedef long long ll;
int T,n,a[N],s[N][25];
int ma,w;
int main(){
	scanf("%d",&T);
	while(T--){
		memset(s,0,sizeof s);
		scanf("%d",&n);
		ma=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(a[i]>ma) ma=a[i];
			s[a[i]][0]++;
		}
		ll ans=0;w=0;
		for(int i=ma;i;i>>=1) w++;
		for(int i=1;i<=ma;i++){
			for(int j=1;j<=w;j++){
				if((i>>(j-1))&1) s[i][j]=s[i][j-1]+s[i-(i>>(j-1))][j-1];
				else s[i][j]=s[i][j-1];
			}
		}
		for(int i=1;i<=ma;i++){
			ans+=1ll*s[i][w]*s[i][0];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 23ms
memory: 99296kb

input:

2
3
1 5 6
3
1 1 1

output:

4
9

result:

ok 2 number(s): "4 9"

Test #2:

score: -100
Wrong Answer
time: 944ms
memory: 99316kb

input:

10
1
1
3321
108907 496886 513637 107549 602502 235745 583320 401703 649106 841450 806050 127630 250786 780434 780387 256680 723365 604626 255396 251497 992405 594166 951810 524404 585892 85571 821715 581042 711296 187617 367585 862536 856196 312147 121285 967957 495031 855565 619680 318939 618420 91...

output:

1
24826
1104
17215
1480
2307
10678
380
86
941

result:

wrong answer 2nd numbers differ - expected: '38911', found: '24826'