QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602993#8719. 后继UESTC_xxx#AC ✓557ms118712kbC++142.3kb2024-10-01 13:58:462024-10-01 13:58:47

Judging History

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

  • [2024-10-01 13:58:47]
  • 评测
  • 测评结果:AC
  • 用时:557ms
  • 内存:118712kb
  • [2024-10-01 13:58:46]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#define LL long long
using namespace std;
const int mod=998244353;
const int Base=23,Base2=27;
inline int lowbit(int x){return x&(-x);}
inline int Jia(int x){return x>=mod?x-mod:x;}
inline int Jian(int x){return x>=0?x:x+mod;}
int KSM(int a,int b){
	int Ans=1;
	while(b){
		if(b&1)Ans=1LL*Ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return Ans;
}
inline int read(){
	int k=0,ty=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')ty=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		k=k*10+ch-'0';
		ch=getchar();
	}
	return k*ty;
}
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
const int maxn=4e5*30+5;
int rt=1,all=1,ch[maxn][2],Size[maxn],id[maxn],ID[maxn][2],v[maxn],n,m;
int a[maxn],pos[maxn],DFN,ans[maxn],To[maxn];
void Insert(int x){
	int p=rt,c;
	for(int i=30;i>=0;--i){
		if(a[x]&(1<<i))c=1;
		else c=0;
		if(!ch[p][c])ch[p][c]=++all;
//		ID[p][c]=x;
		if(ch[p][0]&&ch[p][1])v[i]=p;
		p=ch[p][c];
	}
	pos[x]=p;To[p]=x;
}
void dfs(int x){
	id[x]=++DFN;Size[x]=1;
	if(ch[x][0])dfs(ch[x][0]);
	if(ch[x][1])dfs(ch[x][1]);
	Size[x]+=Size[ch[x][0]]+Size[ch[x][1]];
}
int Get(int x,int deep){
	if(deep==-1)return To[x];
	if(ch[x][ans[deep]^1])return Get(ch[x][ans[deep]^1],deep-1);
	return Get(ch[x][ans[deep]],deep-1);
}
void Solve(){
	for(int i=0;i<=30;++i){
//		cout<<i<<'\n';
		if(!v[i])ans[i]=0;
		else {
//			cout<<"SHIT\n";
			int p=v[i];
			int p2=Get(ch[p][0],i-1);
//			cout<<p<<' '<<p2<<'\n';
			cout<<"? "<<p2<<'\n';
			cout.flush();
			int t,t2=ch[p][1];
			cin>>t;
//			cout<<t<<'\n';
//			cout<<"FAFAFFA\n";
			if(t==-1){
				ans[i]=1;
				continue;
			}
//			cout<<"F1\n";
			t=pos[t];
//			cout<<"F2\n";
			if(id[t2]<=id[t]&&id[t2]+Size[t2]>id[t])ans[i]=0;
			else ans[i]=1;
		}
	}
//	cout<<"FAFAF\n";
	int Ans=0;
	for(int i=30;i>=0;--i){
//		cout<<ans[i]<<'\n';
		Ans=Ans+(ans[i]<<i);
	}
	cout<<"! "<<Ans<<'\n';
	cout.flush();
}
int main(){
//	n=read();m=read();
	std::ios::sync_with_stdio(false);
//	cin.tie(0);
	cin>>n>>m;
//	cout<<n<<' '<<m<<'\n';
	for(int i=1;i<=n;++i){
		cin>>a[i];
		Insert(i);
	}
//	cout<<"AFA\n";
	dfs(rt);
//	cout<<"FAF\n";
	for(int i=1;i<=m;++i){
		Solve();
	}
	cout.flush();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 15848kb

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: 3ms
memory: 15932kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 3ms
memory: 15924kb

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
7
1
-1
-1
7
10
7
2
3
-1
3
1
10
-1
2
2
3
1
10
-1
2
2
3
2
6
4
-1
-1
7
10
7
2
3
-1
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
? 4
? 5
? 10
? 10
! 286523392
? 4
? 9
? 4
? 5
? 10
? 6
! 278134784
? 4
? 9
? 3
? 5
? 10
? 10
! 28311552
? 4
? 9
? 3
? 5
? 10
? 10
! 28311552
? 4
? 9
? 3
? 5
? 10
? 10
! 293601280
? 4
? 9
? 4
? 5
? 10
? 6
! 278134784
?...

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 43ms
memory: 16004kb

input:

100 3000
416322873 449728250 688705913 946343465 16202884 153238658 573284215 724198910 577719053 868106680 951494055 942341618 190594266 331719623 856324110 977865755 151782935 163752541 1565918 870244322 299691610 37854919 198293342 152446496 549402023 869857831 869628458 573984494 162791133 94423...

output:

? 11
? 85
? 88
? 86
? 87
? 62
? 99
? 37
? 37
? 65
? 65
? 44
? 41
! 184027136
? 11
? 85
? 88
? 86
? 87
? 62
? 99
? 60
? 100
? 32
? 32
? 44
? 55
! 445644800
? 11
? 85
? 88
? 86
? 87
? 62
? 99
? 37
? 99
? 65
? 99
? 92
? 70
! 145555456
? 11
? 85
? 88
? 86
? 87
? 62
? 99
? 37
? 99
? 65
? 65
? 44
? 41
! 1...

result:

ok 3000 numbers

Test #5:

score: 0
Accepted
time: 557ms
memory: 118712kb

input:

400000 3000
406697044 910508999 785308673 89872855 911511537 786066190 569035255 791369083 231783630 373589094 1005702647 785128281 910883228 612232307 428493618 691767283 288087749 380834477 1012471581 807583302 951439706 172399529 651163374 395700503 212381194 528978756 628513589 230244101 1046447...

output:

? 27940
? 399271
? 399676
? 174820
? 336368
? 140936
? 19930
? 56556
? 399998
? 400000
? 399999
? 32002
? 193282
? 193282
? 376313
? 376313
? 186229
? 376313
? 376313
? 373848
? 339629
? 35681
? 168297
? 168297
? 250446
? 117192
? 372194
? 304394
? 304394
? 248810
! 140702791
? 27940
? 399271
? 3996...

result:

ok 3000 numbers

Test #6:

score: 0
Accepted
time: 355ms
memory: 74728kb

input:

400000 3000
49852143 106643027 78538081 13535110 34673790 361240760 358287062 285333122 15578697 106130051 320170693 107023555 72813915 2799162 286900401 787319 332890808 75095435 110215229 74827421 107485420 300695656 71750101 285593446 37660664 397030779 392989831 16018850 14036294 361777963 11269...

output:

? 84919
? 84919
? 362252
? 390033
? 241324
? 241324
? 67818
? 252662
? 61474
? 311594
? 180220
? 180220
? 267392
? 38445
? 38445
? 38445
? 38445
? 38445
? 38445
? 38445
! 113099425
? 84919
? 400000
? 362252
? 233261
? 7912
? 233261
? 233261
? 233261
? 359973
? 364726
? 234579
? 234579
? 391729
? 107...

result:

ok 3000 numbers

Extra Test:

score: 0
Extra Test Passed