QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66104#1458. Binary Search AlgorithmeyiigjknWA 3ms3616kbC++141.2kb2022-12-06 19:44:242022-12-06 19:44:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-06 19:44:27]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3616kb
  • [2022-12-06 19:44:24]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
int a[8010],b[8010],fa[8010],lc[8010],rc[8010],dis[8010];
bool cmp[8010][8010];
void query(int tot)
{
	printf("%d",tot);
	for(int i=1;i<=tot;i++) printf(" %d",a[i]);
	puts("");fflush(stdout);
	for(int i=1;i<=tot;i++) scanf("%d",&b[i]);
}
void pushup(int x)
{
	if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]);
	dis[x]=dis[rc[x]]+1;
}
int merge(int x,int y)
{
	if(!x || !y) return x+y;
	if(cmp[y][x]) swap(x,y);
	fa[rc[x]=merge(rc[x],y)]=x;
	pushup(x);
	return x;
}
int main()
{
	int n,x,rt=0;
	char op[10];
	cin>>n;
	fill(dis+1,dis+n+1,1);
	for(int i=0;i<2*n;i++)
	{
		scanf("%s%d",op,&x);
		if(op[0]=='a')
		{
			int tot=0;
			a[++tot]=x;
			for(int i=rt;i;i=rc[i]) a[++tot]=i;
			query(tot);
			for(int i=1;i<=tot;i++)
				for(int j=1;j<=tot;j++)
					cmp[b[i]][b[j]]=(i<j);
			rt=merge(rt,x);
		}
		else
		{
			int tot=0;
			for(int i=lc[rt];i;i=rc[i]) a[++tot]=i;
			for(int i=rc[rt];i;i=rc[i]) a[++tot]=i;
			query(tot);
			int t=merge(lc[x],rc[x]);
			fa[t]=fa[x];
			if(!fa[x]) rt=t;
			else if(lc[fa[x]]==x) lc[fa[x]]=t;
			else rc[fa[x]]=t;
			for(int i=fa[t];i;i=fa[i]) pushup(i);
		}
		printf("%d\n",rt?rt:-1);fflush(stdout);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 3616kb

input:

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


output:

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

result:

wrong answer WA in query 3 queried element 1 was not from S