QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#806521#1458. Binary Search Algorithm_lhy_WA 1ms4144kbC++141.8kb2024-12-09 11:18:292024-12-09 11:18:34

Judging History

This is the latest submission verdict.

  • [2024-12-09 11:18:34]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4144kb
  • [2024-12-09 11:18:29]
  • Submitted

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);
    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;
    }
    set<int> tmp;
    for(auto to:ned)
        tmp.insert(to);
    ned.clear();
    for(auto to:tmp)
        pushup(to);
    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: 0ms
memory: 3852kb

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: 4144kb

input:

10
add 9

add 4
9 4
add 6
9 6
delete 9
4 6
add 7
7 6
delete 4

output:

0 
9
2 4 9 
9
2 6 9 
9
2 4 6 
4
2 6 7 
4
2 0 7 

result:

wrong answer > 2