#line 1 "main.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1078" #include #include #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 3 "/home/user/Library/utils/two_satisfiability.hpp" #include #include #line 2 "/home/user/Library/graph/strongly_connected_components.hpp" #include #line 4 "/home/user/Library/graph/transpose_graph.hpp" /** * @param g is an adjacent list of a digraph * @note $O(V + E)$ * @see https://en.wikipedia.org/wiki/Transpose_graph */ std::vector > make_transpose_graph(std::vector > const & g) { int n = g.size(); std::vector > h(n); REP (i, n) { for (int j : g[i]) { h[j].push_back(i); } } return h; } #line 7 "/home/user/Library/graph/strongly_connected_components.hpp" /** * @brief strongly connected components decomposition, Kosaraju's algorithm / 強連結成分分解 * @return the pair (the number k of components, the function from vertices of g to components) * @param g is an adjacent list of a digraph * @param g_rev is the transpose graph of g * @note $O(V + E)$ */ std::pair > decompose_to_strongly_connected_components(const std::vector > & g, const std::vector > & g_rev) { int n = g.size(); std::vector acc(n); { std::vector used(n); std::function dfs = [&](int i) { used[i] = true; for (int j : g[i]) if (not used[j]) dfs(j); acc.push_back(i); }; REP (i,n) if (not used[i]) dfs(i); reverse(ALL(acc)); } int size = 0; std::vector component_of(n); { std::vector used(n); std::function rdfs = [&](int i) { used[i] = true; component_of[i] = size; for (int j : g_rev[i]) if (not used[j]) rdfs(j); }; for (int i : acc) if (not used[i]) { rdfs(i); ++ size; } } return { size, move(component_of) }; } std::pair > decompose_to_strongly_connected_components(const std::vector > & g) { return decompose_to_strongly_connected_components(g, make_transpose_graph(g)); } #line 6 "/home/user/Library/utils/two_satisfiability.hpp" /** * @brief 2-SAT ($O(N)$) * @param n is the number of variables * @param cnf is a proposition in a conjunctive normal form. Each literal is expressed as number $x$ s.t. $1 \le \vert x \vert \le n$ * @return a vector with the length $n$ if SAT. It's empty if UNSAT. */ std::vector compute_two_satisfiability(int n, const std::vector > & cnf) { // make digraph std::vector > g(2 * n); auto index = [&](int x) { assert (x != 0 and abs(x) <= n); return x > 0 ? x - 1 : n - x - 1; }; for (auto it : cnf) { int x, y; std::tie(x, y) = it; // x or y g[index(- x)].push_back(index(y)); // not x implies y g[index(- y)].push_back(index(x)); // not y implies x } // do SCC std::vector component = decompose_to_strongly_connected_components(g).second; std::vector valuation(n); REP3 (x, 1, n + 1) { if (component[index(x)] == component[index(- x)]) { // x iff not x return std::vector(); // unsat } valuation[x - 1] = component[index(x)] > component[index(- x)]; // use components which indices are large } return valuation; } #line 6 "main.cpp" using namespace std; vector > solve(int n, vector & s, vector & t, vector & u) { auto var = [&](int y, int x) { return y * n + x; }; vector > cnf; REP (y, n) { REP (x, n) { int a = var(s[y], x) + 1; int b = var(x, t[y]) + 1; if (u[y] == 0) { cnf.emplace_back(a, b); } else if (u[y] == 1) { cnf.emplace_back(- a, b); } else if (u[y] == 2) { cnf.emplace_back(a, - b); } else if (u[y] == 3) { cnf.emplace_back(- a, - b); } else { assert (false); } } } auto ev = compute_two_satisfiability(n * n, cnf); if (ev.empty()) { return vector >(); } else { vector > a(n, vector(n)); REP (y, n) { REP (x, n) { a[y][x] = ev[var(y, x)]; } } return a; } } int main() { // input int n; scanf("%d", &n); vector s(n); REP (i, n) { scanf("%d", &s[i]); -- s[i]; } vector t(n); REP (i, n) { scanf("%d", &t[i]); -- t[i]; } vector u(n); REP (i, n) { scanf("%d", &u[i]); } // solve auto a = solve(n, s, t, u); // output if (a.empty()) { printf("%d\n", -1); } else { REP (y, n) { REP (x, n) { printf("%d%c", (int)a[y][x], x + 1 < n ? ' ' : '\n'); } } } return 0; }