Submission #1653135

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=2e5;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
bool c[N];
int a[4][N],n;
inline void add(int x) { while (x<=n) c[x]^=1,x+=x&-x; }
inline bool sum(int x) { int ans=0; while (x) ans^=c[x],x^=x&-x; return ans; }
inline bool solve(int m) {
	bool o=0;int i,t;
	for (i=1;i<=n;i++) c[i]=0;
	for (i=m;i>0;i-=2) {
		for (t=a[2][i]/3+1;t;t^=t&-t) o^=c[t];
		for (t=a[2][i]/3+1;t<=n;t+=t&-t) c[t]^=1;
	}
	return o;
}
int main()
{
	int i,j,t;n=gi();
	bool A=0,B=0,AA=0,BB=0;
	for (i=1;i<=3;i++)
		for (j=1;j<=n;j++)
			a[i][j]=gi();
	for (i=1;i<=n;i++) {
		t=a[2][i]/3+1;
		if (a[1][i]>a[2][i]) (i&1?A:B)^=1;
		if (!((a[1][i]==t*3-2&&a[2][i]==t*3-1&&a[3][i]==t*3)||(a[1][i]==t*3&&a[2][i]==t*3-1&&a[3][i]==t*3-2))||((t&1)!=(i&1)))
			return puts("No"),0;
	}
	AA=solve(n-!(n&1));
	BB=solve(n^(n&1));
	if (AA^B) puts("No");
	else if (BB^A) puts("No");
	else puts("Yes");
	return 0;
}

Submission Info

Judge Result