RT,赛时一直 WA 4 个点,球大佬帮忙看下哪里写挂了 QAQ
思路大概是如果序列里有任何一对奇数距离<2,则整个序列可以随便移动;否则只有长度>=3 的偶数段能动,然后和目标序列比对。感觉做法和题解应该一样的(?)
#include<bits/stdc++.h>
#define il inline
using namespace std;
il int read()
{
int xr=0,F=1;char cr=getchar();
while(cr<'0'||cr>'9') {if(cr=='-') F=-1;cr=getchar();}
while(cr>='0'&&cr<='9')
xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
return xr*F;
}
const int N=2e5+5;
int n,a[N],b[N],c[N],d[N];
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=c[i]=read();
for(int i=1;i<=n;i++) b[i]=d[i]=read();
sort(c+1,c+n+1),sort(d+1,d+n+1);//排序后相等
for(int i=1;i<=n;i++) if(c[i]!=d[i]){printf("No\n");return 0;}
bool flag=0;
bool hv=0;
for(int i=1;i<=n;i++) if(a[i]%2==0) hv=1;
if(!hv)//全是奇数则不能移动
{
for(int i=1;i<=n;i++) if(a[i]!=b[i]){printf("No\n");return 0;}
printf("Yes\n");return 0;
}
for(int i=2;i<=n;i++)
{
//if(a[i]) hv=1;
if((a[i]&1)&&((a[i-1]&1)||(a[i-2]&1))) flag=1;
}
if(!flag)//原序列奇数不能移动
{
int lst=0;a[n+1]=b[n+1]=1;
for(int i=1;i<=n+1;i++)
{
if(a[i]&1)
{
//cout<<"qwq "<<lst<<" "<<i<<endl;
if(a[i]!=b[i]) {printf("No\n");return 0;}
if(lst!=i-3) sort(a+lst+1,a+i),sort(b+lst+1,b+i);
for(int k=lst+1;k<i;k++)
{
if(a[k]!=b[k])
{
printf("No\n");
return 0;
}
}
lst=i;
}
}
printf("Yes\n");
return 0;
}
bool fg=0;
for(int i=2;i<=n;i++)//目标序列的奇数能否移动
{
if((b[i]&1)&&((b[i-1]&1)||(b[i-2]&1))) fg=1;
}
if(fg) printf("Yes\n");
else printf("No\n");
return 0;
}
/*
7
1 2 6 4 1 8 3
4 1 6 1 2 8 3
*/