QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227778#6631. Maximum Bitwise ORugly2333WA 68ms6004kbC++201.0kb2023-10-27 23:02:402023-10-27 23:02:40

Judging History

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

  • [2023-10-27 23:02:40]
  • 评测
  • 测评结果:WA
  • 用时:68ms
  • 内存:6004kb
  • [2023-10-27 23:02:40]
  • 提交

answer

//Δ_A 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111111;
int n,q,a[N],f[N][22];
vector<pair<int,int> > v;
int main(){
	int T,i,j,x,y,s,o;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		for(i=1;i<=n;i++)
			scanf("%d",a+i);
		v.clear();
		for(i=1;i<=n;i++)
			for(x=1;x<=a[i];x<<=1)
				v.push_back(make_pair(a[i]-x,i));
		sort(v.begin(),v.end());
		for(i=1;i<=n;i++)
			f[i][0]=a[i];
		for(j=1;j<=20;j++)
			for(i=1;i<=n;i++)
				if(i+(1<<(j-1))<=n)
					f[i][j]=f[i][j-1]|f[i+(1<<(j-1))][j-1];
		while(q--){
			scanf("%d%d",&x,&y);
			s=0;
			for(j=20,i=x;i<=y;j--)
				if(i+(1<<j)<=y+1)
					s|=f[i][j],i+=1<<j;
			if(s==0)
				printf("0 0\n");
			else{
				o=(1<<(32-__builtin_clz(s)))-1;
				printf("%d ",o);
				s^=o;
				if(!s)
					o=0;
				else{
					i=lower_bound(v.begin(),v.end(),make_pair(s,x))-v.begin();
					if(i<v.size()&&v[i].first==s&&v[i].second<=y)
						o=1;
					else
						o=2;
				}
				printf("%d\n",o);
			}
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5864kb

input:

1
3 2
10 10 5
1 2
1 3

output:

15 2
15 0

result:

ok 4 number(s): "15 2 15 0"

Test #2:

score: 0
Accepted
time: 49ms
memory: 6004kb

input:

100000
1 1
924704060
1 1
1 1
149840457
1 1
1 1
515267304
1 1
1 1
635378394
1 1
1 1
416239424
1 1
1 1
960156404
1 1
1 1
431278082
1 1
1 1
629009153
1 1
1 1
140374311
1 1
1 1
245014761
1 1
1 1
445512399
1 1
1 1
43894730
1 1
1 1
129731646
1 1
1 1
711065534
1 1
1 1
322643984
1 1
1 1
482420443
1 1
1 1
20...

output:

1073741823 2
268435455 2
536870911 2
1073741823 2
536870911 2
1073741823 2
536870911 2
1073741823 2
268435455 2
268435455 2
536870911 2
67108863 2
134217727 2
1073741823 2
536870911 2
536870911 2
268435455 2
536870911 2
536870911 2
536870911 2
268435455 2
268435455 2
1073741823 2
16777215 2
10737418...

result:

ok 200000 numbers

Test #3:

score: 0
Accepted
time: 60ms
memory: 3804kb

input:

50000
2 2
924896435 917026400
1 2
1 2
2 2
322948517 499114106
1 2
2 2
2 2
152908571 242548777
1 1
1 2
2 2
636974385 763173214
1 2
1 1
2 2
164965132 862298613
1 1
1 2
2 2
315078033 401694789
1 2
1 2
2 2
961358343 969300127
2 2
1 2
2 2
500628228 28065329
1 2
1 2
2 2
862229381 863649944
1 2
2 2
2 2
541...

output:

1073741823 2
1073741823 2
536870911 2
536870911 2
268435455 2
268435455 2
1073741823 2
1073741823 2
268435455 2
1073741823 2
536870911 2
536870911 2
1073741823 2
1073741823 2
536870911 2
536870911 2
1073741823 2
1073741823 2
1073741823 2
268435455 2
536870911 2
536870911 2
1073741823 2
1073741823 2
...

result:

ok 200000 numbers

Test #4:

score: -100
Wrong Answer
time: 68ms
memory: 5928kb

input:

33333
3 3
925088809 339284112 289540728
3 3
1 3
1 1
3 3
422399522 892365243 216341776
3 3
3 3
1 2
3 3
668932010 837523227 840095874
1 3
1 3
3 3
3 3
731584574 357877180 359063739
1 1
1 1
3 3
3 3
463358343 833924976 847087403
2 3
3 3
1 2
3 3
377154649 772000701 656357011
2 3
1 2
2 3
3 3
977492169 5540...

output:

536870911 2
1073741823 2
1073741823 2
268435455 2
268435455 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
536870911 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
67108863 2
1073741823 2
1073741...

result:

wrong answer 5770th numbers differ - expected: '1', found: '2'