QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#602974	#8719. 后继	liguo^#	WA	1ms	3944kb	C++20	2.1kb	2024-10-01 13:52:05	2024-10-01 13:52:06

Judging History

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

[2024-10-01 13:52:06]
评测

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

查看

[2024-10-01 13:52:05]
提交

answer

#include <bits/stdc++.h>
using namespace std;
struct node{
    int lson=0,rson=0,dep=0,ed=0,val=0;
}nd[12000006];
int cnt=0;
void add(int num,int id){
    int now=0;
    for(int i=29;i>=0;i--){
        if(num&(1<<i)){
            if(nd[now].rson==0){
                nd[now].rson=++cnt;
                nd[cnt].dep=i;
                nd[cnt].val=nd[now].val+(1<<i);
            }
            now=nd[now].rson;
        }
        else{
            if(nd[now].lson==0){
                nd[now].lson=++cnt;
                nd[cnt].dep=i;
                nd[cnt].val=nd[now].val;
            }
            now=nd[now].lson;
        }
    }
    nd[now].ed=id;
}
int x=0,a[400005];
int diff[32]={0};
int findmax(int now,int d){
    if(d==0)
        return now;
    if(nd[now].rson==0) return findmax(nd[now].lson,d-1);
    if(nd[now].lson==0) return findmax(nd[now].rson,d-1);
    if(x&(1<<(d-1))!=0)
        return findmax(nd[now].lson,d-1);
    if(x&(1<<(d-1))==0)
        return findmax(nd[now].rson,d-1);
}
int findmin(int now,int d){
    if(d==0)
        return now;
    if(nd[now].rson==0) return findmin(nd[now].lson,d-1);
    if(nd[now].lson==0) return findmin(nd[now].rson,d-1);
    if(x&(1<<(d-1))!=0)
        return findmin(nd[now].rson,d-1);
    if(x&(1<<(d-1))==0)
        return findmin(nd[now].lson,d-1);
}
int main(){
    int n,m;scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        add(a[i],i);
    }
    for(int i=1;i<=cnt;i++){
        if(diff[nd[i].dep])
            continue;
        if(nd[i].lson!=0&&nd[i].rson!=0)
            diff[nd[i].dep]=i;
    }
    for(int t=1;t<=m;t++){
    	x=0; 
        for(int i=0;i<=30;i++){
            if(diff[i]==0)
                continue;
            int a1=findmax(nd[diff[i]].lson,i-1);
            int a2=findmin(nd[diff[i]].rson,i-1);
            printf("? %d\n",nd[a1].ed);
            fflush(stdout);
            int res;scanf("%d",&res);
            if(res!=nd[a2].ed)
                x|=(1<<(i-1));
        }
        printf("! %d\n",x);
        fflush(stdout);
    }
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3880kb

input:

output:

? 2
? 1
? 1
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3944kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 1ms

memory: 3868kb

input:

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

output:

? 4
? 8
? 3
? 5
? 1
? 7
! 296747008
? 4
? 8
? 3
? 5
? 1
? 7
! 296747008
? 4
? 8
? 3
? 5
? 1
? 7
! 297009152
? 4
? 8
? 3
? 5
? 1
? 7
! 297009152
? 4
? 8
? 3
? 5
? 1
? 7
! 296747008
? 4
? 8
? 3
? 5
? 1
? 7
! 296747008
? 4
? 8
? 3
? 5
? 1
? 7
! 293601280
? 4
? 8
? 3
? 5
? 1
? 7
! 297009152
? 4
? 8
? 3
...

result:

wrong answer 1st numbers differ - expected: '271581184', found: '296747008'