QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#805212 | #1458. Binary Search Algorithm | cwfxlh | WA | 1ms | 3576kb | C++14 | 1.1kb | 2024-12-08 14:35:33 | 2024-12-08 14:35:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,mnv[50003],lf[50003],rk[50003],stk[50003],tot,k1,k2,k3;
void build(int now,int l,int r){
if(l==r){lf[l]=now;return;}
build(now*2,l,((l+r)>>1));
build(now*2+1,((l+r)>>1)+1,r);
return;
}
string s;
void pushup(int now){
if(mnv[now*2]==0||mnv[now*2+1]==0)mnv[now]=(mnv[now*2]|mnv[now*2+1]);
else{
if(rk[mnv[now*2]]<rk[mnv[now*2+1]])mnv[now]=mnv[now*2];
else mnv[now]=mnv[now*2+1];
}
return;
}
int main(){
cin>>n;
build(1,1,n);
for(int uuu=1;uuu<=2*n;uuu++){
cin>>s>>k1;
if(s[0]=='a')mnv[lf[k1]]=k1;
else mnv[lf[k1]]=0;
stk[tot=1]=mnv[lf[k1]];
for(int i=lf[k1];i!=1;i/=2)stk[++tot]=mnv[i^1];
sort(stk+1,stk+tot+1);
for(int i=1,j=0;i<=tot;i++){
if(stk[i]!=0&&(j==0||stk[j]!=stk[i]))stk[++j]=stk[i];
if(i==tot)tot=j;
}
cout<<tot<<'\n';
fflush(stdout);
for(int i=1;i<=tot;i++)cout<<stk[i]<<' ';
cout<<'\n';
fflush(stdout);
for(int i=1;i<=tot;i++){
cin>>k1;
rk[k1]=i;
}
for(int i=lf[k1];i!=1;i/=2)pushup(i/2);
if(mnv[1]==0)cout<<-1<<'\n';
else cout<<mnv[1]<<'\n';
fflush(stdout);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
3 add 1 1 add 3 3 1 delete 1 3 add 2 3 2 delete 3 2 delete 2
output:
1 1 1 2 1 3 3 1 3 3 2 2 3 3 1 2 2 0 -1
result:
ok n=3, OK
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3576kb
input:
10 add 9 9 add 4 9 4 add 6 9 4 6 delete 9 4 6 add 7 7 9 4 6 delete 4 7 add 5 7 5 add 8 7 9 5 8 add 10 7 10 5 delete 8 7 9 5 add 3 3 7 5 add 2 3 7 5 2 delete 6 3 7 9 delete 10 3 7 delete 7 3 10 add 1 3 7 1 5 2 delete 1 3 7 5 2 delete 3 7 5 2 delete 5 7 2 delete 2 7 5
output:
1 9 9 2 4 9 9 3 4 6 9 9 2 4 6 9 4 4 6 7 9 7 1 7 7 2 5 7 7 4 5 7 8 9 7 3 5 7 10 7 3 5 7 9 7 3 3 5 7 7 4 2 3 5 7 3 3 3 7 9 3 2 3 7 3 2 3 10 3 5 1 2 3 5 7 3 4 2 3 5 7 3 3 2 5 7 7 2 2 7 7 2 5 7 7
result:
wrong answer WA after query 4 found 9, answer is 4