QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66104 | #1458. Binary Search Algorithm | eyiigjkn | WA | 3ms | 3616kb | C++14 | 1.2kb | 2022-12-06 19:44:24 | 2022-12-06 19:44:27 |
Judging History
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