QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66103#1458. Binary Search AlgorithmeyiigjknTL 0ms0kbC++141.2kb2022-12-06 19:43:112022-12-06 19:43:14

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-12-06 19:43:14]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2022-12-06 19:43:11]
  • Submitted

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);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

3
add 1
1

output:

1 1

result: