QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #803615 | #1458. Binary Search Algorithm | peimuda | ML | 1ms | 3716kb | C++14 | 3.5kb | 2024-12-07 17:47:55 | 2024-12-07 17:47:56 |
Judging History
answer
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
int rt;
int ls[8003],rs[8003];
int fa[8003];
int md[8003];
//bool in[8003];
int cv[8003];
void upd(int x)
{
// cout<<"Ud "<<x<<endl;
if(ls[x]>=0&&rs[x]>=0)
{
md[x]=min(md[ls[x]],md[rs[x]])+1;
if(cv[ls[x]]>cv[rs[x]]) swap(ls[x],rs[x]);
}
else
{
md[x]=0;
if(rs[x]>=0) swap(ls[x],rs[x]);
}
if(ls[x]>=0) fa[ls[x]]=x;
if(rs[x]>=0) fa[rs[x]]=x;
}
void upm(int x)
{
if(x==-1) return;
if(ls[x]>=0&&rs[x]>=0) md[x]=min(md[ls[x]],md[rs[x]])+1;
else md[x]=0;
upm(fa[x]);
}
int main()
{
ios_base::sync_with_stdio(0);
int n;
cin>>n;
rt=-1;
string tp;
int x;
n*=2;
int cs=0;
while(n--)
{
cin>>tp>>x;
x--;
if(tp=="add")
{
cs++;
ls[x]=-1;
rs[x]=-1;
if(rt==-1)
{
cout<<0<<endl;
cout.flush();
rt=x;
}
else
{
vector<int> v;
v.push_back(rt);
v.push_back(x);
vector<int> g;
int j;
// cout<<"Sta "<<rt<<endl;
for(j=rt;rs[j]!=-1;)
{
// cout<<"Oh "<<j<<" "<<ls[j]<<' '<<rs[j]<<endl;
if(j==0) exit(-1);
v.push_back(ls[j]);
v.push_back(rs[j]);
g.push_back(j);
if(md[ls[j]]<=md[rs[j]]) j=ls[j];
else j=rs[j];
}
if(ls[j]>=0) v.push_back(ls[j]);
g.push_back(j);
cout<<v.size();
for(int i:v) cout<<' '<<i+1;
cout<<endl;
cout.flush();
for(int i=0;i<v.size();i++)
{
int o;
cin>>o;
o--;
cv[o]=i;
}
rs[j]=x;
int i;
for(i=g.size()-1;i>=0;i--)
{
if(cv[g[i]]<cv[x]) break;
int s=g[i];
if(i>0)
{
if(ls[g[i-1]]==s) ls[g[i-1]]=x;
else rs[g[i-1]]=x;
}
else rt=x;
swap(ls[x],ls[s]);
swap(rs[x],rs[s]);
if(ls[x]==x) ls[x]=s;
else rs[x]=s;
upd(s);
}
upd(x);
for(;i>=0;i--) upd(g[i]);
}
fa[rt]=-1;
}
else
{
cs--;
if(cs==0)
{
cout<<0<<endl;
cout.flush();
rt=-1;
}
else
{
vector<int> v;
vector<int> g;
int j;
int rf=fa[x];
if(rf!=-1)
{
if(ls[rf]==x&&rs[rf]!=-1) v.push_back(rs[rf]);
if(rs[rf]==x&&ls[rf]!=-1) v.push_back(ls[rf]);
}
for(j=x;ls[j]!=-1;j=ls[x])
{
v.push_back(ls[j]);
if(rs[j]>=0) v.push_back(rs[j]);
g.push_back(ls[j]);
}
cout<<v.size();
for(int i:v) cout<<' '<<i+1;
cout<<endl;
cout.flush();
for(int i=0;i<v.size();i++)
{
int o;
cin>>o;
o--;
cv[o]=i;
}
// cout<<"Oh "<<g.size()<<endl;
for(int i=0;i<g.size();i++)
{
int s=g[i];
if(fa[x]!=-1)
{
if(ls[fa[x]]==x) ls[fa[x]]=s;
else rs[fa[x]]=s;
}
else rt=s;
fa[s]=fa[x];
fa[x]=s;
ls[x]=ls[s];
ls[s]=x;
swap(rs[x],rs[s]);
}
if(ls[fa[x]]==x) ls[fa[x]]=-1;
else rs[fa[x]]=-1;
for(int i=((int)g.size())-1;i>=0;i--) upd(g[i]);
if(rf>=0) upd(rf);
if(g.size()) upm(fa[g[0]]);
else upm(rf);
fa[rt]=-1;
}
}
// for(int i=0;i<5;i++) cout<<ls[i]<<' ';
// cout<<endl;
// for(int i=0;i<5;i++) cout<<rs[i]<<' ';
// cout<<endl;
// for(int i=0;i<5;i++) cout<<fa[i]<<' ';
// cout<<endl;
// for(int i=0;i<5;i++) cout<<md[i]<<' ';
// cout<<endl;
if(rt==-1) cout<<"-1"<<endl;
else cout<<rt+1<<endl;
cout.flush();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3716kb
input:
3 add 1 add 3 3 1 delete 1 add 2 3 2 delete 3 2 delete 2
output:
0 1 2 1 3 3 0 3 2 3 2 3 1 2 2 0 -1
result:
ok n=3, OK
Test #2:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
10 add 9 add 4 9 4 add 6 9 4 6 delete 9 4 6 add 7 7 4 6 delete 4 6 add 5 7 5 6 add 8 7 5 8 6 add 10 7 10 5 8 6 delete 8 5 add 3 3 7 10 5 6 add 2 3 7 6 2 delete 6 7 2 delete 10 5 delete 7 5 2 add 1 3 1 5 2 delete 1 5 2 delete 3 5 2 delete 5 2 delete 2
output:
0 9 2 9 4 9 3 9 6 4 9 2 4 6 4 3 4 7 6 7 1 6 7 3 7 5 6 7 4 7 8 5 6 7 5 7 10 5 6 8 7 1 5 7 5 7 3 10 6 5 3 4 3 2 7 6 3 2 7 2 3 1 5 3 2 2 5 3 4 3 1 5 2 3 2 2 5 3 2 5 2 5 1 2 2 0 -1
result:
ok n=10, OK
Test #3:
score: -100
Memory Limit Exceeded
input:
100 add 81 add 96 81 96 add 94 81 94 96 add 32 81 94 32 96 add 35 81 94 32 35 96 add 59 81 94 59 96 add 50 81 50 94 59 96 add 57 81 50 57 94 59 96 add 39 39 81 50 57 94 59 96 add 55 39 81 50 94 55 96 add 23 39 81 50 94 23 55 96 add 40 39 81 40 94 32 35 add 5 39 81 40 94 32 35 5 add 2 39 81 40 94 35...
output:
0 81 2 81 96 81 3 81 94 96 81 4 81 32 94 96 81 5 81 35 94 96 32 81 4 81 59 94 96 81 5 81 50 94 59 96 81 6 81 57 50 94 59 96 81 7 81 39 50 94 57 96 59 39 6 39 55 81 94 50 96 39 7 39 23 81 94 50 55 96 39 6 39 40 81 94 32 35 39 7 39 5 81 40 94 35 32 39 6 39 2 81 40 94 35 39 1 96 39 7 39 12 81 40 50 23 ...