QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#805212#1458. Binary Search AlgorithmcwfxlhWA 1ms3576kbC++141.1kb2024-12-08 14:35:332024-12-08 14:35:33

Judging History

This is the latest submission verdict.

  • [2024-12-08 14:35:33]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3576kb
  • [2024-12-08 14:35:33]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int n,mnv[50003],lf[50003],rk[50003],stk[50003],tot,k1,k2,k3;
void build(int now,int l,int r){
	if(l==r){lf[l]=now;return;}
	build(now*2,l,((l+r)>>1));
	build(now*2+1,((l+r)>>1)+1,r);
	return;
}
string s;
void pushup(int now){
	if(mnv[now*2]==0||mnv[now*2+1]==0)mnv[now]=(mnv[now*2]|mnv[now*2+1]);
	else{
		if(rk[mnv[now*2]]<rk[mnv[now*2+1]])mnv[now]=mnv[now*2];
		else mnv[now]=mnv[now*2+1];
	}
	return;
}
int main(){
	cin>>n;
	build(1,1,n);
	for(int uuu=1;uuu<=2*n;uuu++){
		cin>>s>>k1;
		if(s[0]=='a')mnv[lf[k1]]=k1;
		else mnv[lf[k1]]=0;
		stk[tot=1]=mnv[lf[k1]];
		for(int i=lf[k1];i!=1;i/=2)stk[++tot]=mnv[i^1];
		sort(stk+1,stk+tot+1);
		for(int i=1,j=0;i<=tot;i++){
			if(stk[i]!=0&&(j==0||stk[j]!=stk[i]))stk[++j]=stk[i];
			if(i==tot)tot=j;
		}
		cout<<tot<<'\n';
		fflush(stdout);
		for(int i=1;i<=tot;i++)cout<<stk[i]<<' ';
		cout<<'\n';
		fflush(stdout);
		for(int i=1;i<=tot;i++){
			cin>>k1;
			rk[k1]=i;
		}
		for(int i=lf[k1];i!=1;i/=2)pushup(i/2);
		if(mnv[1]==0)cout<<-1<<'\n';
		else cout<<mnv[1]<<'\n';
		fflush(stdout);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
add 1
1
add 3
3 1
delete 1
3
add 2
3 2
delete 3
2
delete 2


output:

1
1 
1
2
1 3 
3
1
3 
3
2
2 3 
3
1
2 
2
0

-1

result:

ok n=3, OK

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3576kb

input:

10
add 9
9
add 4
9 4
add 6
9 4 6
delete 9
4 6
add 7
7 9 4 6
delete 4
7
add 5
7 5
add 8
7 9 5 8
add 10
7 10 5
delete 8
7 9 5
add 3
3 7 5
add 2
3 7 5 2
delete 6
3 7 9
delete 10
3 7
delete 7
3 10
add 1
3 7 1 5 2
delete 1
3 7 5 2
delete 3
7 5 2
delete 5
7 2
delete 2
7 5

output:

1
9 
9
2
4 9 
9
3
4 6 9 
9
2
4 6 
9
4
4 6 7 9 
7
1
7 
7
2
5 7 
7
4
5 7 8 9 
7
3
5 7 10 
7
3
5 7 9 
7
3
3 5 7 
7
4
2 3 5 7 
3
3
3 7 9 
3
2
3 7 
3
2
3 10 
3
5
1 2 3 5 7 
3
4
2 3 5 7 
3
3
2 5 7 
7
2
2 7 
7
2
5 7 
7

result:

wrong answer WA after query 4 found 9, answer is 4