QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#806539 | #1458. Binary Search Algorithm | _lhy_ | WA | 1ms | 3860kb | C++14 | 2.1kb | 2024-12-09 11:28:41 | 2024-12-09 11:28:46 |
Judging History
answer
#include<bits/stdc++.h>
#define N 8005
#define ls ((p)<<1)
#define rs (((p)<<1)|1)
using namespace std;
int n,mi[N<<2],ans[N],pos[N];
char ch[N];
set<int> S,ned;
bitset<N> q[N],xiao[N];
void pushup(int p)
{
if(!p) return ;
if(q[mi[ls]][mi[rs]])
{
if(xiao[mi[ls]][mi[rs]]) mi[p]=mi[ls];
else mi[p]=mi[rs];
pushup(p>>1);
}
else ned.insert(p);
}
void update(int p,int L,int R,int pos,int c)
{
if(L==R)
{
mi[p]=c;
pushup(p>>1);
return ;
}
int mid=(L+R)>>1;
if(mid>=pos) update(ls,L,mid,pos,c);
else update(rs,mid+1,R,pos,c);
}
void query()
{
printf("%d ",S.size());
for(auto to:S)
printf("%d ",to);
printf("\n");
fflush(stdout);
for(int i=1;i<=S.size();i++)
scanf("%d",&ans[i]),pos[ans[i]]=i;
}
void work()
{
int x;
scanf("%s%d",ch+1,&x);
if(ch[1]=='a') update(1,1,n,x,x);
else update(1,1,n,x,0);
set<int> tmp;
while(ned.size())
{
int p=*(--ned.end());
ned.erase(p);
if(q[mi[ls]][mi[rs]])
pushup(p);
else
tmp.insert(p);
}
ned=tmp;
S.clear();
for(auto p:ned)
{
// printf("%d:%d->%d\n",p,mi[ls],mi[rs]);
// cout<<q[mi[ls]][mi[rs]]<<endl;
S.insert(mi[ls]);
S.insert(mi[rs]);
q[mi[ls]][mi[rs]]=q[mi[rs]][mi[ls]]=1;
}
query();
for(auto p:ned)
{
if(pos[mi[ls]]<pos[mi[rs]]) xiao[mi[ls]][mi[rs]]=1,xiao[mi[rs]][mi[ls]]=0;
else xiao[mi[ls]][mi[rs]]=0,xiao[mi[rs]][mi[ls]]=1;
}
tmp.clear();
while(ned.size())
{
int p=*(--ned.end());
ned.erase(p);
if(q[mi[ls]][mi[rs]])
pushup(p);
else
tmp.insert(p);
}
ned=tmp;
if(mi[1]==0) puts("-1");
else printf("%d\n",mi[1]);
fflush(stdout);
}
int main()
{
scanf("%d",&n);
q[0][0]=1;
for(int i=1;i<=n;i++)
q[i][0]=q[0][i]=1,xiao[i][0]=1,xiao[0][i]=0,q[i][i]=1;
for(int i=1;i<=2*n;i++)
work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
3 add 1 add 3 3 1 delete 1 add 2 3 2 delete 3 delete 2
output:
0 1 2 1 3 3 0 3 2 2 3 3 0 2 0 -1
result:
ok n=3, OK
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3792kb
input:
10 add 9 add 4 9 4 add 6 9 6 delete 9 4 6 add 7 7 6 delete 4 add 5 7 5 add 8 7 8 add 10 7 10 delete 8 add 3 3 5 add 2 3 7 2 delete 6 delete 10 delete 7 add 1 1 2 delete 1 delete 3 5 2 delete 5 delete 2
output:
0 9 2 4 9 9 2 6 9 9 2 4 6 4 2 6 7 4 0 7 2 5 7 7 2 7 8 7 2 7 10 7 0 7 2 3 5 7 3 2 3 7 3 0 3 0 3 0 3 2 1 2 3 0 3 2 2 5 5 0 2 0 -1
result:
wrong answer WA after query 5 found 4, answer is 7