6925 2023. 12. 19 22:46:31 111 Pac-Man cpp17 Elfogadva 100/100 1.769s 199324 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

#define pii pair<int, int>

void bad() {
	cout << "NO" << '\n';
	exit(0);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	vector<int> X(N), Y(N), Z(N);
	for (int i = 0; i < N; i++) {
		cin >> X[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> Y[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> Z[i];
	}
	map<tuple<int, int, int>, int> s;
	for (int i = 0; i < N; i++) {
		s[{X[i], Y[i], Z[i]}] = i;
	}
	map<pii, vector<int>> xy, yz, zx;
	for (int i = 0; i < N; i++) {
		xy[{X[i], Y[i]}].push_back(Z[i]);
		yz[{Y[i], Z[i]}].push_back(X[i]);
		zx[{Z[i], X[i]}].push_back(Y[i]);
	}
	for (auto& [p, v] : xy) {
		sort(v.begin(), v.end());
	}
	for (auto& [p, v] : yz) {
		sort(v.begin(), v.end());
	}
	for (auto& [p, v] : zx) {
		sort(v.begin(), v.end());
	}
	// same line
	for (int i = 0; i < N; i++) {
		vector<pair<vector<int>&, int>> a = {
			{xy[{X[i], Y[i]}], Z[i]},
			{yz[{Y[i], Z[i]}], X[i]},
			{zx[{Z[i], X[i]}], Y[i]},
		};
		for (auto [v, x] : a) {
			auto t = lower_bound(v.begin(), v.end(), x);
			if (t != v.begin()) {
				if (*prev(t) != *t - 1) {
					bad();
				}
			}
			if (next(t) != v.end()) {
				if (*next(t) != *t + 1) {
					bad();
				}
			}
		}
	}
	// same plane
	map<int, map<int, pii>> xp, yp, zp;
	for (int i = 0; i < N; i++) {
		xp[X[i]][Y[i]];
		yp[Y[i]][Z[i]];
		zp[Z[i]][X[i]];
	}
	for (auto& [x, m] : xp) {
		pii a = {INT_MAX, INT_MIN};
		for (auto t = m.begin(); t != m.end(); t++) {
			t->second = a;
			a.first = min(a.first, xy[{x, t->first}].front());
			a.second = max(a.second, xy[{x, t->first}].back());
		}
	}
	for (auto& [y, m] : yp) {
		pii a = {INT_MAX, INT_MIN};
		for (auto t = m.begin(); t != m.end(); t++) {
			t->second = a;
			a.first = min(a.first, yz[{y, t->first}].front());
			a.second = max(a.second, yz[{y, t->first}].back());
		}
	}
	for (auto& [z, m] : zp) {
		pii a = {INT_MAX, INT_MIN};
		for (auto t = m.begin(); t != m.end(); t++) {
			t->second = a;
			a.first = min(a.first, zx[{z, t->first}].front());
			a.second = max(a.second, zx[{z, t->first}].back());
		}
	}
	map<int, map<int, pii>> xs, ys, zs;
	for (int i = 0; i < N; i++) {
		xs[X[i]][Y[i]];
		ys[Y[i]][Z[i]];
		zs[Z[i]][X[i]];
	}
	for (auto& [x, m] : xs) {
		pii a = {INT_MAX, INT_MIN};
		for (auto t = m.rbegin(); t != m.rend(); t++) {
			t->second = a;
			a.first = min(a.first, xy[{x, t->first}].front());
			a.second = max(a.second, xy[{x, t->first}].back());
		}
	}
	for (auto& [y, m] : ys) {
		pii a = {INT_MAX, INT_MIN};
		for (auto t = m.rbegin(); t != m.rend(); t++) {
			t->second = a;
			a.first = min(a.first, yz[{y, t->first}].front());
			a.second = max(a.second, yz[{y, t->first}].back());
		}
	}
	for (auto& [z, m] : zs) {
		pii a = {INT_MAX, INT_MIN};
		for (auto t = m.rbegin(); t != m.rend(); t++) {
			t->second = a;
			a.first = min(a.first, zx[{z, t->first}].front());
			a.second = max(a.second, zx[{z, t->first}].back());
		}
	}
	for (int i = 0; i < N; i++) {
		if (xp[X[i]][Y[i]].first < Z[i]) {
			if (!s.count({X[i], Y[i] - 1, Z[i]}) && !s.count({X[i], Y[i], Z[i] - 1})) {
				bad();
			}
		}
		if (xp[X[i]][Y[i]].second > Z[i]) {
			if (!s.count({X[i], Y[i] - 1, Z[i]}) && !s.count({X[i], Y[i], Z[i] + 1})) {
				bad();
			}
		}
		if (xs[X[i]][Y[i]].first < Z[i]) {
			if (!s.count({X[i], Y[i] + 1, Z[i]}) && !s.count({X[i], Y[i], Z[i] - 1})) {
				bad();
			}
		}
		if (xs[X[i]][Y[i]].second > Z[i]) {
			if (!s.count({X[i], Y[i] + 1, Z[i]}) && !s.count({X[i], Y[i], Z[i] + 1})) {
				bad();
			}
		}
		if (yp[Y[i]][Z[i]].first < X[i]) {
			if (!s.count({X[i] - 1, Y[i], Z[i]}) && !s.count({X[i], Y[i], Z[i] - 1})) {
				bad();
			}
		}
		if (yp[Y[i]][Z[i]].second > X[i]) {
			if (!s.count({X[i] + 1, Y[i], Z[i]}) && !s.count({X[i], Y[i], Z[i] - 1})) {
				bad();
			}
		}
		if (ys[Y[i]][Z[i]].first < X[i]) {
			if (!s.count({X[i] - 1, Y[i], Z[i]}) && !s.count({X[i], Y[i], Z[i] + 1})) {
				bad();
			}
		}
		if (ys[Y[i]][Z[i]].second > X[i]) {
			if (!s.count({X[i] + 1, Y[i], Z[i]}) && !s.count({X[i], Y[i], Z[i] + 1})) {
				bad();
			}
		}
		if (zp[Z[i]][X[i]].first < Y[i]) {
			if (!s.count({X[i] - 1, Y[i], Z[i]}) && !s.count({X[i], Y[i] - 1, Z[i]})) {
				bad();
			}
		}
		if (zp[Z[i]][X[i]].second > Y[i]) {
			if (!s.count({X[i] - 1, Y[i], Z[i]}) && !s.count({X[i], Y[i] + 1, Z[i]})) {
				bad();
			}
		}
		if (zs[Z[i]][X[i]].first < Y[i]) {
			if (!s.count({X[i] + 1, Y[i], Z[i]}) && !s.count({X[i], Y[i] - 1, Z[i]})) {
				bad();
			}
		}
		if (zs[Z[i]][X[i]].second > Y[i]) {
			if (!s.count({X[i] + 1, Y[i], Z[i]}) && !s.count({X[i], Y[i] + 1, Z[i]})) {
				bad();
			}
		}
	}
	// check connectivity
	vector<int> v(N);
	auto dfs = [&](auto dfs, int i) {
		if (v[i]) {
			return;
		}
		v[i] = true;
		if (s.count({X[i] + 1, Y[i], Z[i]})) {
			dfs(dfs, s[{X[i] + 1, Y[i], Z[i]}]);
		}
		if (s.count({X[i] - 1, Y[i], Z[i]})) {
			dfs(dfs, s[{X[i] - 1, Y[i], Z[i]}]);
		}
		if (s.count({X[i], Y[i] + 1, Z[i]})) {
			dfs(dfs, s[{X[i], Y[i] + 1, Z[i]}]);
		}
		if (s.count({X[i], Y[i] - 1, Z[i]})) {
			dfs(dfs, s[{X[i], Y[i] - 1, Z[i]}]);
		}
		if (s.count({X[i], Y[i], Z[i] + 1})) {
			dfs(dfs, s[{X[i], Y[i], Z[i] + 1}]);
		}
		if (s.count({X[i], Y[i], Z[i] - 1})) {
			dfs(dfs, s[{X[i], Y[i], Z[i] - 1}]);
		}
	};
	dfs(dfs, 0);
	if (count(v.begin(), v.end(), true) != N) {
		bad();
	}
	cout << "YES" << '\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1960 KiB
2 Elfogadva 3ms 2188 KiB
3 Elfogadva 3ms 2648 KiB
subtask2 18/18
4 Elfogadva 3ms 2716 KiB
5 Elfogadva 3ms 3036 KiB
6 Elfogadva 3ms 3284 KiB
7 Elfogadva 3ms 3280 KiB
8 Elfogadva 3ms 3464 KiB
9 Elfogadva 3ms 3572 KiB
10 Elfogadva 3ms 3820 KiB
11 Elfogadva 3ms 3760 KiB
12 Elfogadva 3ms 3760 KiB
13 Elfogadva 3ms 4052 KiB
subtask3 19/19
14 Elfogadva 16ms 8916 KiB
15 Elfogadva 3ms 4228 KiB
16 Elfogadva 9ms 6192 KiB
17 Elfogadva 10ms 6392 KiB
18 Elfogadva 64ms 9412 KiB
19 Elfogadva 61ms 9148 KiB
20 Elfogadva 3ms 4260 KiB
21 Elfogadva 7ms 5632 KiB
22 Elfogadva 13ms 6532 KiB
23 Elfogadva 12ms 6644 KiB
24 Elfogadva 12ms 6608 KiB
25 Elfogadva 61ms 9244 KiB
26 Elfogadva 3ms 4264 KiB
subtask4 24/24
27 Elfogadva 195ms 51212 KiB
28 Elfogadva 17ms 8160 KiB
29 Elfogadva 1.106s 107792 KiB
30 Elfogadva 1.111s 115116 KiB
31 Elfogadva 1.157s 107760 KiB
32 Elfogadva 1.1s 108896 KiB
33 Elfogadva 4ms 5552 KiB
34 Elfogadva 219ms 51816 KiB
35 Elfogadva 1.161s 102008 KiB
36 Elfogadva 208ms 52028 KiB
37 Elfogadva 1.243s 100988 KiB
38 Elfogadva 465ms 77400 KiB
39 Elfogadva 4ms 5380 KiB
subtask5 22/22
40 Elfogadva 186ms 39560 KiB
41 Elfogadva 4ms 5040 KiB
42 Elfogadva 43ms 14344 KiB
43 Elfogadva 150ms 34296 KiB
44 Elfogadva 1.291s 71172 KiB
45 Elfogadva 1.332s 72496 KiB
46 Elfogadva 3ms 5032 KiB
47 Elfogadva 3ms 4800 KiB
48 Elfogadva 28ms 11256 KiB
49 Elfogadva 140ms 31372 KiB
50 Elfogadva 149ms 34404 KiB
51 Elfogadva 162ms 34156 KiB
52 Elfogadva 1.264s 73272 KiB
53 Elfogadva 3ms 4780 KiB
subtask6 17/17
54 Elfogadva 423ms 90884 KiB
55 Elfogadva 1.769s 199324 KiB
56 Elfogadva 175ms 36604 KiB
57 Elfogadva 165ms 34872 KiB
58 Elfogadva 158ms 35572 KiB
59 Elfogadva 1.291s 72948 KiB
60 Elfogadva 1.149s 159152 KiB
61 Elfogadva 177ms 37316 KiB
62 Elfogadva 163ms 35312 KiB
63 Elfogadva 163ms 35304 KiB
64 Elfogadva 1.279s 72204 KiB
65 Elfogadva 1.286s 72592 KiB
66 Elfogadva 221ms 71264 KiB