QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#602754	#8719. 后继	Kanate^#	WA	1ms	7656kb	C++14	1.5kb	2024-10-01 12:37:42	2024-10-01 12:37:44

Judging History

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

[2024-10-01 12:37:44]
评测

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

查看

[2024-10-01 12:37:42]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// 1073741823 1
const int N = 4e5 + 7;
int n  , m ;
int cnt = 0 ;
struct node {
	int son[2],dep,id;
}t[N*31];
int F[N];
int belong[N];
int ans[31];
void ins(int now,int x,int id,int len){
	t[now].dep = len ;
    t[now].id = id;
	if(len==0) {
		belong[id] = now;
		return ;
	}
	bool nxt = x & (1<<len-1);
	if(t[now].son[nxt] == 0) {
		t[now].son[nxt] = ++ cnt;
		if(t[now].son[0] && t[now].son[1]){
		    F[len] = now;
		}
	}
    ins(t[now].son[nxt],x,id,len-1);
}

int find(int x,bool mx){
	if(t[x].dep == 0){
		return x;
	}
	bool nx = mx ^ ans[t[x].dep];
	if(t[x].son[nx]) return find(t[x].son[nx],mx);
	else return t[x].son[!nx];
}

int query(int x){
	cout << "? " << x << endl;
	cout.flush();
	cin >> x;
    if(x==-1) x=  0 ;
	return x;
}

int solve(int y){
	if(F[y] == 0) return 0;
	int x = F[y];
	int ls = find(x,0); // 0 最小值 
	int rs = find(x,1); // 1 最大值
	int Q = query(t[rs].id);
	if(belong[Q] == ls)
		ans[y] = 1;
	else 
		ans[y] = 0 ;
	return 0;
}


int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m ;
    cnt = 1;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		ins(1,x,i,30);
	}
  //  cout << cnt << endl;
	while(m-->0){
		for(int i=1;i<=30;i++) ans[i] = 0 ;
		for(int i=1;i<=30;i++) solve(i);
		int x = 0;
		for(int i=1;i<=30;i++){
			if(ans[i]) x = x | (1<<i-1); 
		}
		cout << "! " << x << endl;
		cout.flush();
	}
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 7656kb

input:

output:

? 5
? 2
? 4
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5604kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 0ms

memory: 7656kb

input:

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

output:

? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0
? 3
? 2
? 7
? 8
? 7
? 9
! 0

result:

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