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 |
---|---|---|---|---|---|---|---|---|---|
#32110 | #1458. Binary Search Algorithm | Wu_Ren | WA | 6ms | 3788kb | C++11 | 1.7kb | 2022-05-17 15:15:21 | 2022-05-17 15:15:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n,tr[32010],rk[8010];
char s[10];
vector<int>v;
void qry(){
printf("%d ",v.size());
for(int i:v) printf("%d ",i);puts("");
fflush(stdout);
for(int i=1,w;i<=v.size();i++) scanf("%d",&w),rk[w]=i;
}
void build(int l,int r,int t){
tr[t]=-1;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,t<<1),build(mid+1,r,t<<1|1);
}
void add(int a,int l,int r,int t){
if(tr[t]>0) v.push_back(tr[t]);
if(l==r) return;
int mid=(l+r)>>1;
if(a<=mid) add(a,l,mid,t<<1);
else add(a,mid+1,r,t<<1|1);
}
void upd_add(int a,int l,int r,int t){
if(tr[t]<0||rk[tr[t]]>rk[a]) tr[t]=a;
if(l==r) return;
int mid=(l+r)>>1;
if(a<=mid) upd_add(a,l,mid,t<<1);
else upd_add(a,mid+1,r,t<<1|1);
}
void del(int a,int l,int r,int t){
if(l==r) return;
int mid=(l+r)>>1;
if(a<=mid){
del(a,l,mid,t<<1);
if(tr[t<<1|1]>0) v.push_back(tr[t<<1|1]);
}
else{
del(a,mid+1,r,t<<1|1);
if(tr[t<<1]>0) v.push_back(tr[t<<1]);
}
}
void upd_del(int a,int l,int r,int t){
if(l==r){
tr[t]=-1;
return;
}
int mid=(l+r)>>1;
if(a<=mid) upd_del(a,l,mid,t<<1);
else upd_del(a,mid+1,r,t<<1|1);
if(tr[t<<1]<0) tr[t]=tr[t<<1|1];
else if(tr[t<<1|1]<0) tr[t]=tr[t<<1];
else tr[t]=rk[tr[t<<1]]<rk[tr[t<<1|1]]?tr[t<<1]:tr[t<<1|1];
}
void dfs(int l,int r,int t){
if(l==r) return;
int mid=(l+r)>>1;
dfs(l,mid,t<<1),dfs(mid+1,r,t<<1|1);
}
int main(){
scanf("%d",&n);
build(1,n,1);
for(int i=1,x;i<=2*n;i++){
scanf("%s%d",s,&x);
if(s[0]=='a'){
v.clear();
v.push_back(x);
add(x,1,n,1);
qry();
upd_add(x,1,n,1);
}
else{
v.clear();
del(x,1,n,1);
qry();
upd_del(x,1,n,1);
}
dfs(1,n,1);
printf("%d\n",tr[1]),fflush(stdout);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 3788kb
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 3 1 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: 6ms
memory: 3788kb
input:
10 add 9 9 add 4 9 4 add 6 9 9 6 delete 9 4 6 add 7 7 4 6 6 6 delete 4 7 add 5 7 5 add 8 7 7 7 8 add 10 7 7 10 delete 8 7 10 5 add 3 3 7 5 add 2 3 3 3 2 delete 6 3 7 10 delete 10 3 7 delete 7 3 add 1 3 3 3 1 2 delete 1 3 5 2 delete 3 5 2 delete 5 2 delete 2
output:
1 9 9 2 4 9 9 3 6 9 9 9 2 6 4 4 5 7 4 6 6 6 7 1 7 7 2 5 7 7 4 8 7 7 7 7 3 10 7 7 7 3 7 10 5 7 3 3 7 5 3 4 2 3 3 3 3 3 7 10 3 3 2 7 3 3 1 3 3 5 1 3 3 3 2 3 3 2 3 5 3 2 2 5 5 1 2 2 0 -1
result:
wrong answer WA in query 3 two of elements to sort were equal