思路:对于每个怪物,往前找 相应的、没用过的、距离当前怪物最近的 药水,捡起来(相当于倒着来)
代码中的 x 数组存药水,f 数组是捡不捡这个药水,num 和 nex 是链表,方便找到每个怪物的 相应的、没用过的、距离当前怪物最近的 药水
时间复杂度 O(n),但是不知道为啥莫名 WA
#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
int k=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
void out(int x)
{
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else out(x/10),putchar(x%10+'0');
}
const int N=2e5+10;
int a[N];
int x[N],len=0;
bool f[N];
int num[N],nex[N];
int main()
{
int n=in();
for(int i=1;i<=n;i++)
{
a[i]=in();
int xx=in();
if(a[i]==1)x[++len]=xx,nex[len]=num[xx],num[xx]=len;
else
{
if(num[xx]==0)out(-1),exit(0);
f[num[xx]]=true;
num[xx]=nex[num[xx]];
}
}
int ans=0,sum=0,u=0;
for(int i=1;i<=n;i++)
if(a[i]==2)ans=max(ans,sum),sum=0;
else if(f[++u])sum++;
out(ans),putchar('\n');
for(int i=1;i<=len;i++)cout<<f[i]<<" ";
return 0;
}