QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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
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'