QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32110#1458. Binary Search AlgorithmWu_RenWA 6ms3788kbC++111.7kb2022-05-17 15:15:212022-05-17 15:15:22

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-17 15:15:22]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 3788kb
  • [2022-05-17 15:15:21]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
int n,tr[32010],rk[8010];
char s[10];
vector<int>v;
void qry(){
	printf("%d ",v.size());
	for(int i:v) printf("%d ",i);puts("");
	fflush(stdout);
	for(int i=1,w;i<=v.size();i++) scanf("%d",&w),rk[w]=i;
}
void build(int l,int r,int t){
	tr[t]=-1;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(l,mid,t<<1),build(mid+1,r,t<<1|1);
}
void add(int a,int l,int r,int t){
	if(tr[t]>0) v.push_back(tr[t]);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(a<=mid) add(a,l,mid,t<<1);
	else add(a,mid+1,r,t<<1|1);
}
void upd_add(int a,int l,int r,int t){
	if(tr[t]<0||rk[tr[t]]>rk[a]) tr[t]=a;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(a<=mid) upd_add(a,l,mid,t<<1);
	else upd_add(a,mid+1,r,t<<1|1);
}
void del(int a,int l,int r,int t){
	if(l==r) return;
	int mid=(l+r)>>1;
	if(a<=mid){
		del(a,l,mid,t<<1);
		if(tr[t<<1|1]>0) v.push_back(tr[t<<1|1]);
	}
	else{
		del(a,mid+1,r,t<<1|1);
		if(tr[t<<1]>0) v.push_back(tr[t<<1]);
	}
}
void upd_del(int a,int l,int r,int t){
	if(l==r){
		tr[t]=-1;
		return;
	}
	int mid=(l+r)>>1;
	if(a<=mid) upd_del(a,l,mid,t<<1);
	else upd_del(a,mid+1,r,t<<1|1);
	if(tr[t<<1]<0) tr[t]=tr[t<<1|1];
	else if(tr[t<<1|1]<0) tr[t]=tr[t<<1];
	else tr[t]=rk[tr[t<<1]]<rk[tr[t<<1|1]]?tr[t<<1]:tr[t<<1|1];
} 
void dfs(int l,int r,int t){
	if(l==r) return;
	int mid=(l+r)>>1;
	dfs(l,mid,t<<1),dfs(mid+1,r,t<<1|1);
}
int main(){
	scanf("%d",&n);
	build(1,n,1);
	for(int i=1,x;i<=2*n;i++){
		scanf("%s%d",s,&x);
		if(s[0]=='a'){
			v.clear();
			v.push_back(x);
			add(x,1,n,1);
			qry();
			upd_add(x,1,n,1);
		}
		else{
			v.clear();
			del(x,1,n,1);
			qry();
			upd_del(x,1,n,1);
		}
		dfs(1,n,1);
		printf("%d\n",tr[1]),fflush(stdout);
	}
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3788kb

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 3 1 
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: 6ms
memory: 3788kb

input:

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


output:

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

result:

wrong answer WA in query 3 two of elements to sort were equal