QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#740634	#8719. 后继	ucup-team4352^#	WA	1ms	5592kb	C++23	1.6kb	2024-11-13 10:49:01	2024-11-13 10:49:02

Judging History

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

[2024-11-13 10:49:02]
评测

测评结果：WA
用时：1ms
内存：5592kb

查看

[2024-11-13 10:49:01]
提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=4e5+5;
int a[maxn];
int ch[maxn*32][2],tot=1;
int bit[35],t[35];
vector<int>id[35];
pii p[maxn];
int n,m;
int find(int x){
	return p[lower_bound(p+1,p+n+1,(pii){x,0})-p].second;
}
bool check(int x,int p){
	int loc=lower_bound(id[x].begin(),id[x].end(),p)-id[x].begin();
	if(loc>=id[x].size()||id[x][loc]!=p)return 0;
	return 1;
}
int query(int x){
	cout<<"? "<<find(x)<<endl;
	int y;
	cin>>y;
	return y;
}
void ins(int x){
	int now=1,num=0;
	for(int i=29;i>=0;i--){
		int tmp=x>>i&1;
		if(ch[now][tmp]==0)ch[now][tmp]=++tot;
		if(ch[now][0]&&ch[now][1]){
			bit[i]=now;
			t[i]=num;
		}
		num^=tmp<<i;
		now=ch[now][tmp];
	}
}
int calc(int x){
	int now=1,num=x;
	for(int i=29;i>=0;i--){
		int tmp=x>>i&1;
		if(ch[now][tmp])now=ch[now][tmp];
		else now=ch[now][tmp^1],num^=1<<i;
	}
	return num;
}
void solv(){
	int x=0;
	for(int i=0;i<30;i++){
		if(bit[i]==0)continue;
		int s=(1<<i)-1;
		int num=calc(x^t[i]^s);
		int q=query(num);
		if(q==-1||check(i,q)==0){
			x^=1<<i;
		}
	}
	cout<<"! "<<x<<endl;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ins(a[i]);
		p[i]={a[i],i};
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<30;j++){
			if(bit[j]==0)continue;
			if((a[i]&t[j])==t[j]&&(a[i]&(1<<j))){
				id[j].push_back(i);
			}
		}
	}
	sort(p+1,p+n+1);
	while(m--)solv();
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t=1;
	// cin>>t;
	while(t--)solve();
	return 0;
}
/*
5 1
1 2 3 4 5
2 1 0 7 6
*/

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5592kb

input:

output:

? 4
? 1
? 1
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5592kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 0ms

memory: 5540kb

input:

10 10
380864879 387438357 21484978 21099484 375657510 23189485 24467021 379687119 386094773 15156199
3
10
-1
1
7
-1
3
1
10
7
-1
-1
7
5
4
1
-1
-1
7
10
4
2
3
4
3
1
10
-1
2
10
3
1
10
-1
2
10
3
2
6
4
-1
-1
7
10
4
2
3
4
6
2
6
8
3
-1
3
2
8
9
6
8

output:

? 4
? 9
? 3
? 5
? 10
? 3
! 271581184
? 4
? 9
? 3
? 5
? 10
? 10
! 296747008
? 4
? 9
? 3
? 5
? 10
? 10
! 288358400
? 4
? 9
? 3
? 5
? 10
? 3
! 279969792
? 4
? 9
? 3
? 5
? 10
? 3
! 279969792
? 4
? 9
? 3
? 5
? 10
? 3
! 279969792
? 4
? 9
? 3
? 5
? 10
? 10
! 293601280
? 4
? 9
? 3
? 5
? 10
? 3
! 279969792
?...

result:

wrong answer 3rd numbers differ - expected: '286523392', found: '288358400'