QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #66105 | #1458. Binary Search Algorithm | eyiigjkn | WA | 16ms | 3944kb | C++14 | 1.2kb | 2022-12-06 19:46:21 | 2022-12-06 19:46:22 |
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[x];i;i=rc[i]) a[++tot]=i;
for(int i=rc[x];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: 100
Accepted
time: 1ms
memory: 3792kb
input:
3 add 1 1 add 3 3 1 delete 1 add 2 3 2 delete 3 2 delete 2
output:
1 1 1 2 3 1 3 0 3 2 2 3 3 1 2 2 0 -1
result:
ok n=3, OK
Test #2:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
10 add 9 9 add 4 9 4 add 6 9 6 delete 9 4 6 add 7 7 4 delete 4 6 add 5 7 5 add 8 7 5 8 add 10 7 10 5 delete 8 add 3 3 7 10 add 2 3 2 delete 6 delete 10 5 delete 7 5 add 1 3 1 2 delete 1 2 delete 3 5 2 delete 5 2 delete 2
output:
1 9 9 2 4 9 9 2 6 9 9 2 4 6 4 2 7 4 7 1 6 7 2 5 7 7 3 8 7 5 7 3 10 7 5 7 0 7 3 3 7 10 3 2 2 3 3 0 3 1 5 3 1 5 3 3 1 3 2 3 1 2 3 2 5 2 5 1 2 2 0 -1
result:
ok n=10, OK
Test #3:
score: -100
Wrong Answer
time: 16ms
memory: 3944kb
input:
100 add 81 81 add 96 81 96 add 94 81 94 add 32 81 94 32 add 35 81 94 35 add 59 81 59 96 add 50 81 50 59 add 57 81 50 57 add 39 39 81 50 57 add 55 39 55 add 23 39 23 55 add 40 39 40 23 add 5 39 40 5 add 2 39 40 5 2 delete 55 add 12 39 12 40 5 delete 40 23 5 add 51 39 12 51 add 65 39 12 65 51 delete ...
output:
1 81 81 2 96 81 81 2 94 81 81 3 32 81 94 81 3 35 81 94 81 3 59 81 96 81 3 50 81 59 81 3 57 81 50 81 4 39 81 50 57 39 2 55 39 39 3 23 39 55 39 3 40 39 23 39 3 5 39 40 39 4 2 39 40 5 39 0 39 4 12 39 40 5 39 2 23 5 39 3 51 39 12 39 4 65 39 12 51 39 0 39 4 69 39 12 65 39 5 81 50 57 12 23 81 4 60 81 50 5...
result:
wrong answer WA after query 142 found 7, answer is 25