結果
問題 | No.2505 matriX cOnstRuction |
ユーザー |
👑 |
提出日時 | 2024-05-25 16:16:27 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 19,088 bytes |
コンパイル時間 | 3,874 ms |
コンパイル使用メモリ | 260,324 KB |
実行使用メモリ | 510,976 KB |
最終ジャッジ日時 | 2024-12-20 19:49:50 |
合計ジャッジ時間 | 15,624 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 WA * 29 |
ソースコード
// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")// #define INTERACTIVE#include <bits/stdc++.h>using namespace std;namespace templates {// typeusing ll = long long;using ull = unsigned long long;using Pii = pair<int, int>;using Pil = pair<int, ll>;using Pli = pair<ll, int>;using Pll = pair<ll, ll>;template <class T>using pq = priority_queue<T>;template <class T>using qp = priority_queue<T, vector<T>, greater<T>>;// clang-format off#define vec(T, A, ...) vector<T> A(__VA_ARGS__);#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));// clang-format on// for loop#define fori1(a) for (ll _ = 0; _ < (a); _++)#define fori2(i, a) for (ll i = 0; i < (a); i++)#define fori3(i, a, b) for (ll i = (a); i < (b); i++)#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))#define overload4(a, b, c, d, e, ...) e#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)// declare and input// clang-format off#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);#define VEC(T, A, n) vector<T> A(n); inp(A);#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);// clang-format on// const valueconst ll MOD1 = 1000000007;const ll MOD9 = 998244353;const double PI = acos(-1);// other macro#if !defined(RIN__LOCAL) && !defined(INTERACTIVE)#define endl "\n"#endif#define spa ' '#define len(A) ll(A.size())#define all(A) begin(A), end(A)// functionvector<char> stoc(string &S) {int n = S.size();vector<char> ret(n);for (int i = 0; i < n; i++) ret[i] = S[i];return ret;}string ctos(vector<char> &S) {int n = S.size();string ret = "";for (int i = 0; i < n; i++) ret += S[i];return ret;}template <class T>auto min(const T &a) {return *min_element(all(a));}template <class T>auto max(const T &a) {return *max_element(all(a));}template <class T, class S>auto clamp(T &a, const S &l, const S &r) {return (a > r ? r : a < l ? l : a);}template <class T, class S>inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S>inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}template <class T, class S>inline bool chclamp(T &a, const S &l, const S &r) {auto b = clamp(a, l, r);return (a != b ? a = b, 1 : 0);}template <typename T>T sum(vector<T> &A) {T tot = 0;for (auto a : A) tot += a;return tot;}template <typename T>vector<T> compression(vector<T> X) {sort(all(X));X.erase(unique(all(X)), X.end());return X;}// input and outputnamespace io {// __int128_tstd::ostream &operator<<(std::ostream &dest, __int128_t value) {std::ostream::sentry s(dest);if (s) {__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = std::end(buffer);do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest;}// vector<T>template <typename T>istream &operator>>(istream &is, vector<T> &A) {for (auto &a : A) is >> a;return is;}template <typename T>ostream &operator<<(ostream &os, vector<T> &A) {for (size_t i = 0; i < A.size(); i++) {os << A[i];if (i != A.size() - 1) os << ' ';}return os;}// vector<vector<T>>template <typename T>istream &operator>>(istream &is, vector<vector<T>> &A) {for (auto &a : A) is >> a;return is;}template <typename T>ostream &operator<<(ostream &os, vector<vector<T>> &A) {for (size_t i = 0; i < A.size(); i++) {os << A[i];if (i != A.size() - 1) os << endl;}return os;}// pair<S, T>template <typename S, typename T>istream &operator>>(istream &is, pair<S, T> &A) {is >> A.first >> A.second;return is;}template <typename S, typename T>ostream &operator<<(ostream &os, pair<S, T> &A) {os << A.first << ' ' << A.second;return os;}// vector<pair<S, T>>template <typename S, typename T>istream &operator>>(istream &is, vector<pair<S, T>> &A) {for (size_t i = 0; i < A.size(); i++) {is >> A[i];}return is;}template <typename S, typename T>ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {for (size_t i = 0; i < A.size(); i++) {os << A[i];if (i != A.size() - 1) os << endl;}return os;}// tupletemplate <typename T, size_t N>struct TuplePrint {static ostream &print(ostream &os, const T &t) {TuplePrint<T, N - 1>::print(os, t);os << ' ' << get<N - 1>(t);return os;}};template <typename T>struct TuplePrint<T, 1> {static ostream &print(ostream &os, const T &t) {os << get<0>(t);return os;}};template <typename... Args>ostream &operator<<(ostream &os, const tuple<Args...> &t) {TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);return os;}// io functionsvoid FLUSH() {cout << flush;}void print() {cout << endl;}template <class Head, class... Tail>void print(Head &&head, Tail &&...tail) {cout << head;if (sizeof...(Tail)) cout << spa;print(std::forward<Tail>(tail)...);}template <typename T, typename S>void prisep(vector<T> &A, S sep) {int n = A.size();for (int i = 0; i < n; i++) {cout << A[i];if (i != n - 1) cout << sep;}cout << endl;}template <typename T, typename S>void priend(T A, S end) {cout << A << end;}template <typename T>void prispa(T A) {priend(A, spa);}template <typename T, typename S>bool printif(bool f, T A, S B) {if (f)print(A);elseprint(B);return f;}template <class... T>void inp(T &...a) {(cin >> ... >> a);}} // namespace iousing namespace io;// read graphvector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {vector<vector<int>> edges(n, vector<int>());for (int i = 0; i < m; i++) {INT(u, v);u -= indexed;v -= indexed;edges[u].push_back(v);if (!direct) edges[v].push_back(u);}return edges;}vector<vector<int>> read_tree(int n, int indexed = 1) {return read_edges(n, n - 1, false, indexed);}template <typename T = long long>vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());for (int i = 0; i < m; i++) {INT(u, v);T w;inp(w);u -= indexed;v -= indexed;edges[u].push_back({v, w});if (!direct) edges[v].push_back({u, w});}return edges;}template <typename T = long long>vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {return read_wedges<T>(n, n - 1, false, indexed);}// yes / nonamespace yesno {// yesinline bool yes(bool f = true) {cout << (f ? "yes" : "no") << endl;return f;}inline bool Yes(bool f = true) {cout << (f ? "Yes" : "No") << endl;return f;}inline bool YES(bool f = true) {cout << (f ? "YES" : "NO") << endl;return f;}// noinline bool no(bool f = true) {cout << (!f ? "yes" : "no") << endl;return f;}inline bool No(bool f = true) {cout << (!f ? "Yes" : "No") << endl;return f;}inline bool NO(bool f = true) {cout << (!f ? "YES" : "NO") << endl;return f;}// possibleinline bool possible(bool f = true) {cout << (f ? "possible" : "impossible") << endl;return f;}inline bool Possible(bool f = true) {cout << (f ? "Possible" : "Impossible") << endl;return f;}inline bool POSSIBLE(bool f = true) {cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;return f;}// impossibleinline bool impossible(bool f = true) {cout << (!f ? "possible" : "impossible") << endl;return f;}inline bool Impossible(bool f = true) {cout << (!f ? "Possible" : "Impossible") << endl;return f;}inline bool IMPOSSIBLE(bool f = true) {cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;return f;}// Alice Bobinline bool Alice(bool f = true) {cout << (f ? "Alice" : "Bob") << endl;return f;}inline bool Bob(bool f = true) {cout << (f ? "Bob" : "Alice") << endl;return f;}// Takahashi Aokiinline bool Takahashi(bool f = true) {cout << (f ? "Takahashi" : "Aoki") << endl;return f;}inline bool Aoki(bool f = true) {cout << (f ? "Aoki" : "Takahashi") << endl;return f;}} // namespace yesnousing namespace yesno;} // namespace templatesusing namespace templates;template <int MAXLOG = 30, typename T = int>struct BinaryTrie {using u64 = unsigned long long;public:struct Node {Node *nxt[2];T cnt;Node() : nxt{nullptr, nullptr}, cnt(T()) {}};Node *root;bool multi;BinaryTrie(bool multi = true) : root(new Node()), multi(multi) {}BinaryTrie(Node *root, bool multi = true) : root(root), multi(multi) {}void insert(u64 bit, T x = T(1), u64 xor_val = 0) {if (!multi) {assert(x == 1);if (x == 1 && count(bit, xor_val) == 1) return;}root = insert(root, bit, x, MAXLOG, xor_val);}void erase(u64 bit, T x = T(1), u64 xor_val = 0) {if (!multi) {assert(x == 1);if (count(bit, xor_val) == 0) return;}insert(root, bit, -x, MAXLOG, xor_val);}Node *find(u64 bit, u64 xor_val = 0) {return find(root, bit, MAXLOG, xor_val);}T count(u64 bit, u64 xor_val = 0) {auto node = find(bit, xor_val);return node ? node->cnt : T();}std::pair<u64, Node *> kth_element(T k, u64 xor_val = 0) {if (k < 0) k = (root->cnt) + k;if (k < 0 || root->cnt <= k) return {-1, nullptr};return kth_element(root, k, MAXLOG, xor_val);}std::pair<u64, Node *> min_element(u64 xor_val = 0) {return kth_element(0, xor_val);}std::pair<u64, Node *> max_element(u64 xor_val = 0) {return kth_element(-1, xor_val);}T lt_count(u64 bit, u64 xor_val = 0) {return count_less(root, bit, MAXLOG, xor_val);}T leq_count(u64 bit, u64 xor_val = 0) {return lt_count(bit, xor_val) + count(bit, xor_val);}T gt_count(u64 bit, u64 xor_val = 0) {return root->cnt - leq_count(bit, xor_val);}T geq_count(u64 bit, u64 xor_val = 0) {return root->cnt - lt_count(bit, xor_val);}~BinaryTrie() {delete root;}private:virtual Node *clone(Node *t) {return t;}Node *insert(Node *t, u64 bit, T x, int depth, u64 xor_val, bool need = true) {if (need) t = clone(t);if (depth == -1) {t->cnt += x;} else {bool f = (xor_val >> depth) & 1;auto &to = t->nxt[f ^ ((bit >> depth) & 1)];if (!to) {to = new Node();need = false;}to = insert(to, bit, x, depth - 1, xor_val, need);t->cnt += x;}return t;}Node *find(Node *t, u64 bit, int depth, u64 xor_val) {if (depth == -1)return t;else {bool f = (xor_val >> depth) & 1;auto &to = t->nxt[f ^ ((bit >> depth) & 1)];return to ? find(to, bit, depth - 1, xor_val) : nullptr;}}std::pair<u64, Node *> kth_element(Node *t, T k, int bit_index, u64 xor_val) {if (bit_index == -1)return {0, t};else {bool f = (xor_val >> bit_index) & 1;if ((t->nxt[f] ? t->nxt[f]->cnt : 0) <= k) {auto res = kth_element(t->nxt[f ^ 1], k - (t->nxt[f] ? t->nxt[f]->cnt : 0),bit_index - 1, xor_val);res.first |= u64(1) << bit_index;return res;} else {return kth_element(t->nxt[f], k, bit_index - 1, xor_val);}}}T count_less(Node *t, u64 bit, int bit_index, u64 xor_val) {if (bit_index == -1) return T();T ret = T();bool f = (xor_val >> bit_index) & 1;if ((bit >> bit_index & 1) && t->nxt[f]) ret += t->nxt[f]->cnt;if (t->nxt[f ^ (bit >> bit_index & 1)])ret += count_less(t->nxt[f ^ (bit >> bit_index & 1)], bit, bit_index - 1, xor_val);return ret;}};/*// type templatestruct S {using u64 = unsigned long long;S() {// e()// write here}S &operator+=(const S &r) {// write herereturn *this;}friend S operator+(S l, const S &r) {return l += r;}S operator-(const S &r) const {// 削除を行う場合に必要return *this;}bool operator==(const int &x) const {// 重複を許さない場合、x == 1 に対して適切な判定を行う// 削除を行う場合、x == 0 に対して適切な判定を行うreturn false;}S(u64 x) {// insert の引数等に与える用// 必要に応じて bit とかを引数に追加する想定}};*/using Node = BinaryTrie<0, ll>::Node;void solve() {INT(n, m);VEC(int, R, n);VEC(int, C, m);VVEC(int, A, n, m);const ll inf = 1LL << 30;Node *root = new Node();auto add = [&](int bit, int x, ll z) {auto node = root;for (int i = 29; i >= 0; i--) {if (node->nxt[0] == nullptr) node->nxt[0] = new Node();if (node->nxt[1] == nullptr) node->nxt[1] = new Node();if (x >> i & 1) {node = node->nxt[1 - (bit >> i & 1)];} else {node->nxt[1 - (bit >> i & 1)]->cnt += z;node = node->nxt[bit >> i & 1];}}};for (int i = 0; i < n; i++) {int ma = 1;while (ma <= R[i]) ma <<= 1;ma--;int x = A[0][0] ^ A[i][0];if (R[i] == 0) {add(x, 1, inf);} else {add(x, 0, 1);add(x, R[i], 1);add(x, ma, inf);}}for (int j = 0; j < m; j++) {int ma = 1;while (ma <= C[j]) ma <<= 1;ma--;int x = A[0][j];if (C[j] == 0) {add(x, 1, inf);} else {add(x, 0, 1);add(x, C[j], 1);add(x, ma, inf);}}ll ans = inf;int r0 = -1;auto dfs = [&](auto &&self, Node *node, ll tot, ll bit, ll t) -> void {if (node == nullptr) {if (chmin(ans, tot)) r0 = bit;return;}tot += node->cnt;self(self, node->nxt[0], tot, bit, t - 1);if (t != 0) self(self, node->nxt[1], tot, bit | (1 << t - 1), t - 1);};dfs(dfs, root, 0, 0, 30);if (ans == inf) {print(-1);return;}vec(int, R_, n);vec(int, C_, m);fori(i, n) {R_[i] = r0 ^ A[i][0] ^ A[0][0];}fori(j, m) {C_[j] = r0 ^ A[0][j];}fori(i, n) fori(j, m) {if ((R_[i] ^ C_[j]) != A[i][j]) {print(-1);return;}}print(ans);}int main() {#ifndef INTERACTIVEcin.tie(0)->sync_with_stdio(0);#endif// cout << fixed << setprecision(12);int t;t = 1;cin >> t;while (t--) solve();return 0;}// // #pragma GCC target("avx2")// // #pragma GCC optimize("O3")// // #pragma GCC optimize("unroll-loops")// // #define INTERACTIVE//// #include "kyopro-cpp/template.hpp"//// #include "data_structure/Binary_Trie.hpp"// using Node = BinaryTrie<0, ll>::Node;//// void solve() {// INT(n, m);// VEC(int, R, n);// VEC(int, C, m);// VVEC(int, A, n, m);//// const ll inf = 1LL << 30;// Node *root = new Node();//// auto add = [&](int bit, int x, ll z) {// auto node = root;// for (int i = 29; i >= 0; i--) {// if (node->nxt[0] == nullptr) node->nxt[0] = new Node();// if (node->nxt[1] == nullptr) node->nxt[1] = new Node();// if (x >> i & 1) {// node = node->nxt[1 - (bit >> i & 1)];// } else {// node->nxt[1 - (bit >> i & 1)]->cnt += z;// node = node->nxt[bit >> i & 1];// }// }// };//// for (int i = 0; i < n; i++) {// int ma = 1;// while (ma <= R[i]) ma <<= 1;// ma--;//// int x = A[0][0] ^ A[i][0];// if (R[i] == 0) {// add(x, 1, inf);// } else {// add(x, 0, 1);// add(x, R[i], 1);// add(x, ma, inf);// }// }// for (int j = 0; j < m; j++) {// int ma = 1;// while (ma <= C[j]) ma <<= 1;// ma--;//// int x = A[0][j];// if (C[j] == 0) {// add(x, 1, inf);// } else {// add(x, 0, 1);// add(x, C[j], 1);// add(x, ma, inf);// }// }//// ll ans = inf;// int r0 = -1;// auto dfs = [&](auto &&self, Node *node, ll tot, ll bit, ll t) -> void {// if (node == nullptr) {// if (chmin(ans, tot)) r0 = bit;// return;// }// tot += node->cnt;// self(self, node->nxt[0], tot, bit, t - 1);// if (t != 0) self(self, node->nxt[1], tot, bit | (1 << t - 1), t - 1);// };//// dfs(dfs, root, 0, 0, 30);// if (ans == inf) {// print(-1);// return;// }//// vec(int, R_, n);// vec(int, C_, m);// fori(i, n) {// R_[i] = r0 ^ A[i][0] ^ A[0][0];// }// fori(j, m) {// C_[j] = r0 ^ A[0][j];// }//// fori(i, n) fori(j, m) {// if ((R_[i] ^ C_[j]) != A[i][j]) {// print(-1);// return;// }// }// print(ans);// }//// int main() {// #ifndef INTERACTIVE// cin.tie(0)->sync_with_stdio(0);// #endif// // cout << fixed << setprecision(12);// int t;// t = 1;// cin >> t;// while (t--) solve();// return 0;// }