#line 1 "main.cpp" /** * @title Template */ #include #include #include #include #include #include #include #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/chmin_chmax.cpp" template constexpr bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template constexpr bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } /** * @title Chmin/Chmax */ #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp" #line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp" class range { public: class iterator { private: int64_t M_position; public: constexpr iterator(int64_t position) noexcept: M_position(position) { } constexpr void operator ++ () noexcept { ++M_position; } constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; } constexpr int64_t operator * () const noexcept { return M_position; } }; class reverse_iterator { private: int64_t M_position; public: constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { } constexpr void operator ++ () noexcept { --M_position; } constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; } constexpr int64_t operator * () const noexcept { return M_position; } }; private: const iterator M_first, M_last; public: constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { } constexpr iterator begin() const noexcept { return M_first; } constexpr iterator end() const noexcept { return M_last; } constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } }; /** * @title Range */ #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/rev.cpp" #include #include #line 6 "/Users/kodamankod/Desktop/cpp_programming/Library/other/rev.cpp" template class rev_impl { public: using iterator = decltype(std::rbegin(std::declval())); private: const iterator M_begin; const iterator M_end; public: constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { } constexpr iterator begin() const noexcept { return M_begin; } constexpr iterator end() const noexcept { return M_end; } }; template constexpr decltype(auto) rev(T &&cont) { return rev_impl(std::forward(cont)); } /** * @title Reverser */ #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/two_sat.cpp" #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network.cpp" #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/adjust_index.cpp" #include #line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/other/adjust_index.cpp" class adjust_index { private: const size_t M_stuff, M_size; public: explicit adjust_index(const size_t stuff, const size_t size): M_stuff(stuff), M_size(size) { } size_t operator [] (const size_t index) const { assert(index < M_size); return M_stuff + index; } size_t to_index(const size_t fixed) const { assert(fixed >= M_stuff); assert(fixed < M_size + M_stuff); return fixed - M_stuff; } size_t size() const { return M_size; } }; /** * @title Index Adjustment */ #line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network.cpp" #line 6 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network.cpp" #include #line 10 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network.cpp" #include #line 12 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network.cpp" template class network { public: using vertex_type = typename Edge::vertex_type; using edge_type = Edge; using size_type = size_t; protected: std::vector> M_graph; public: explicit network() = default; explicit network(const size_type size) { add_vertices(size); } template typename std::enable_if::type add_vertex() { vertex_type res = M_graph.size(); M_graph.push_back({ }); return res; } template typename std::enable_if::type add_vertex() { M_graph.push_back({ }); } template typename std::enable_if::type add_vertices(const size_type size) { size_type cur = M_graph.size(); M_graph.resize(cur + size); return adjust_index(cur, size); } template typename std::enable_if::type add_vertices(const size_type size) { size_type cur = M_graph.size(); M_graph.resize(cur + size); } void add_edge(const edge_type &edge) { M_graph[edge.source].push_back(edge); } template void emplace_edge(const vertex_type src, Args&&... args) { M_graph[src].emplace_back(src, std::forward(args)...); } std::vector &operator [] (const vertex_type vert) { assert(vert < size()); return M_graph[vert]; } const std::vector &operator [] (const vertex_type vert) const { assert(vert < size()); return M_graph[vert]; } size_type size() const { return M_graph.size(); } bool empty() const { return M_graph.empty(); } void clear() { M_graph.clear(); M_graph.shrink_to_fit(); } }; class base_edge { public: using vertex_type = uint32_t; const vertex_type source, dest; explicit base_edge(const vertex_type source, const vertex_type dest): source(source), dest(dest) { } base_edge reverse() const { return base_edge(dest, source); } }; template class flow_edge: public base_edge { public: using vertex_type = typename base_edge::vertex_type; using flow_type = Flow; flow_type flow; const flow_type capacity; explicit flow_edge(const base_edge &edge, const flow_type capacity): base_edge(edge), flow(0), capacity(capacity) { } explicit flow_edge(const base_edge &edge, const flow_type flow, const flow_type capacity): base_edge(edge), flow(flow), capacity(capacity) { } explicit flow_edge(const vertex_type source, const vertex_type dest, const flow_type capacity): base_edge(source, dest), flow(0), capacity(capacity) { } explicit flow_edge(const vertex_type source, const vertex_type dest, const flow_type flow, const flow_type capacity): base_edge(source, dest), flow(flow), capacity(capacity) { } flow_edge reverse() const { return flow_edge(static_cast(*this).reverse(), capacity - flow, capacity); } }; /** * @title Network */ #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/scc.cpp" #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/fix_point.cpp" #line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/fix_point.cpp" template struct fix_point_impl: private Func { explicit constexpr fix_point_impl(Func &&func): Func(std::forward(func)) { } template constexpr decltype(auto) operator () (Args &&... args) const { return Func::operator()(*this, std::forward(args)...); } }; template constexpr decltype(auto) fix_point(Func &&func) { return fix_point_impl(std::forward(func)); } /** * @title Lambda Recursion */ #line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/scc.cpp" #line 6 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/scc.cpp" #include template class strongly_connected_components { public: using network_type = Network; using vertex_type = typename Network::vertex_type; using edge_type = typename Network::edge_type; using size_type = typename Network::size_type; private: std::vector> graph; std::vector> revgraph; public: explicit strongly_connected_components(const network_type &net) { graph.resize(net.size()); revgraph.resize(net.size()); for (size_type src = 0; src < net.size(); ++src) { for (const auto &edge: net[src]) { graph[src].push_back(edge.dest); revgraph[edge.dest].push_back(src); } } } std::vector> decompose() const { std::vector visited(graph.size()); std::stack topological; const auto sort = fix_point([&](auto dfs, const vertex_type u) -> void { if (visited[u]) return; visited[u] = true; for (const auto v: graph[u]) { dfs(v); } topological.push(u); }); for (vertex_type src = 0; src < graph.size(); ++src) { sort(src); } std::vector> group; const auto decompose = fix_point([&](const auto dfs, const vertex_type u) -> void { if (visited[u]) return; visited[u] = true; group.back().push_back(u); for (const auto v: revgraph[u]) { dfs(v); } }); std::fill(visited.begin(), visited.end(), false); while (!topological.empty()) { const auto u = topological.top(); topological.pop(); if (!visited[u]) { group.push_back({ }); decompose(u); } } return group; } }; /** * @title Strongly Connected Components */ #line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/two_sat.cpp" #line 10 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/two_sat.cpp" class two_sat { public: using size_type = size_t; private: network graph; public: explicit two_sat() = default; explicit two_sat(const size_type size): graph(size * 2) { } void add_clause(const size_type i, const bool f, const size_type j, const bool g) { assert(i < size()); assert(j < size()); graph.emplace_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0)); graph.emplace_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0)); } std::pair> satisfy() const { const auto groups = strongly_connected_components(graph).decompose(); std::vector id(graph.size()); std::vector res(size()); for (size_type i = 0; i < groups.size(); ++i) { for (const auto x: groups[i]) { id[x] = i; } } for (size_type i = 0; i < size(); ++i) { if (id[2 * i] == id[2 * i + 1]) { return { false, { } }; } res[i] = id[2 * i] < id[2 * i + 1]; } return { true, res }; } size_type size() const { return graph.size() / 2; } }; /** * @title Two Sat */ #line 18 "main.cpp" using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; constexpr i32 inf32 = (i32(1) << 30) - 1; constexpr i64 inf64 = (i64(1) << 62) - 1; int main() { size_t N; std::cin >> N; std::vector S(N), T(N); std::vector U(N); for (auto &x: S) { std::cin >> x; --x; } for (auto &x: T) { std::cin >> x; --x; } for (auto &x: U) { std::cin >> x; } two_sat sat(N * N); for (auto i: range(0, N)) { for (auto j: range(0, N)) { const auto u = S[i] * N + j; const auto v = j * N + T[i]; switch (U[i]) { case 0: sat.add_clause(u, true, v, true); break; case 1: sat.add_clause(u, false, v, true); break; case 2: sat.add_clause(u, true, v, false); break; case 3: sat.add_clause(u, false, v, false); break; default: break; } } } const auto [satisfiable, answer] = sat.satisfy(); if (!satisfiable) { std::cout << "-1\n"; } else { for (auto i: range(0, N)) { for (auto j: range(0, N)) { std::cout << answer[i * N + j] << (j + 1 == N ? '\n' : ' '); } } } return 0; }