QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#740634#8719. 后继ucup-team4352#WA 1ms5592kbC++231.6kb2024-11-13 10:49:012024-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
*/

詳細信息

Test #1:

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

input:

5 1
1 2 3 4 5
-1
5
5

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'