Submission #1781413

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 100000;

int n;
int a[3][MaxN + 1];

int pos[MaxN + 1];

int filp[2], rev[2];

bool book[MaxN + 1];

inline bool solve()
{
	for (int i = 1; i <= n; ++i)
	{
		int b[3];
		for (int k = 0; k < 3; ++k)
			b[k] = a[k][i];
		sort(b, b + 3);

		if (b[2] % 3 || b[1] != a[1][i])
			return false;
		if (b[2] - b[1] != 1 || b[1] - b[0] != 1)
			return false;

		pos[i] = b[2] / 3;
		if (pos[i] - i & 1)
			return false;

		if (a[0][i] > a[2][i])
			filp[i & 1] ^= 1;
	}

	for (int i = 1; i <= n; ++i)
		if (!book[i])
		{
			int x = pos[i];
			while (x != i)
			{
				book[x] = true;
				rev[i & 1] ^= 1;
				x = pos[x];
			}
		}

	return filp[0] == rev[1] && rev[0] == filp[1];
}

int main()
{
	cin >> n;
	for (int k = 0; k < 3; ++k)
		for (int i = 1; i <= n; ++i)
			a[k][i] = getint();

	puts(solve() ? "Yes" : "No");

	return 0;
}

Submission Info

Judge Result