QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780294#9745. 递增序列Zpair#WA 38ms3904kbC++201.0kb2024-11-25 09:46:072024-11-25 09:46:13

Judging History

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

  • [2024-11-25 09:46:13]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:3904kb
  • [2024-11-25 09:46:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;ll k,a[N];
int op[70][2];
ll ans[70];
void solve(){
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	for(int i=0;i<=60;++i)
		op[i][0]=op[i][1]=0,ans[i]=0;
	for(int i=2;i<=n;++i){
		ll x=a[i-1],y=a[i];
		for(int j=60;j>=0;--j){
			ll vx=((x>>j)&1);
			ll vy=((y>>j)&1);
			if(vx==vy)continue;
			if(vx<vy)op[j][0]=1;
			if(vx>vy)op[j][1]=1;
			break;
		}
	}
	for(int i=0;i<=60;++i){
		ll lst=(i?ans[i-1]:1);
		if(op[i][0]&&op[i][1])
			ans[i]=0;
		else if(op[i][0]||op[i][1])
			ans[i]=lst;
		else ans[i]=lst*2;
	}
	ll sum=0;
	for(int i=60;i>=0;--i){
		if(op[i][0]&&op[i][1]){
			puts("0");
			return;
		}
		ll vk=((k>>i)&1);
		if(op[i][0]){
			if(vk==1){
				sum+=(i?ans[i-1]:1);
				break;
			}
		}
		else if(op[i][1]){
			if(vk==0)
				break;
		}
		else{
			if(vk==1)
				sum+=(i?ans[i-1]:1);
		}
	}
	printf("%lld\n",sum);
}
int main(){
	int T;cin>>T;
	while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3904kb

input:

1
4 17
3 2 5 16

output:

4

result:

ok single line: '4'

Test #2:

score: -100
Wrong Answer
time: 38ms
memory: 3764kb

input:

36156
2 732025001343805266
563399128172323734 55283226774627822
7 388099190813067712
564150557919527813 457487771983557281 332055400678110195 760833651510929158 785768483273197875 690506113272551236 463276585748519124
2 798714574862593347
426890163990834364 434764725667883272
1 414708220571820990
42...

output:

288230376151711744
0
432345564227567616
414708220571820990
716398192192370637
0
1949654914769743
0
0
0
811009189367843522
0
0
0
114457959388827197
36028797018963968
0
0
91540211282631658
0
694703231769895639
144115188075855872
0
0
0
0
432345564227567616
65333152962117910
753346372609875092
180143985...

result:

wrong answer 4th lines differ - expected: '414708220571820991', found: '414708220571820990'