Why WA#14
查看原帖
Why WA#14
765934
hujiasheng1234楼主2024/10/1 16:38
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mx=1e5+5;
int t,n,a[mx],aa[mx],b[mx],c[mx],aj[mx],bj[mx];
int ret1,ret2;
void s(int l,int r,int a[],long long &ans){
	if(l==r) return ;
	int mid=(l+r)/2;
	int i=l,j=mid+1,tot=l;
	s(l,mid,a,ans);
	s(mid+1,r,a,ans);
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]){
			c[tot++]=a[i];
			i++;
		}
		else{
			ans+=mid-i+1;
			c[tot++]=a[j];
			j++;
		}
	}
	while(i<=mid) c[tot++]=a[i++];
	while(j<=r) c[tot++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=c[i];
}
void slove(){
	memset(aj,0,sizeof(aj));
	memset(bj,0,sizeof(bj));
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),aj[a[i]]++;
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]),bj[b[i]]++;
	for(int i=1;i<=n;i++){
		if(aj[a[i]]!=bj[a[i]]){
			puts("NO");
			return ;
		}
	}
	long long ans1=0,ans2=0;
	s(1,n,a,ans1),s(1,n,b,ans2);
	if(abs(ans1-ans2)%2==0) puts("YES");
	else puts("NO");
}
signed main(){
    scanf("%lld",&t);
	while(t--) slove(); 
    return 0;
}
2024/10/1 16:38
加载中...