結果
| 問題 | No.2505 matriX cOnstRuction |
| ユーザー |
 suisen
|
| 提出日時 | 2023-07-26 21:45:49 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
WA
(最新)
J_ERR
(最初)
|
| 実行時間 | - |
| コード長 | 6,480 bytes |
| コンパイル時間 | 4,747 ms |
| コンパイル使用メモリ | 148,028 KB |
| 最終ジャッジ日時 | 2025-02-15 19:20:19 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 WA * 63 |
ソースコード
#include <algorithm>#include <array>#include <bit>#include <cassert>#include <concepts>#include <cstdint>#include <iostream>#include <iterator>#include <numeric>#include <tuple>#include <vector>int KthBit(const std::integral auto x, const int k) {return x >> k & 1;}void Solve() {static constexpr int kMaxNM = 50000, kDigits = 30;int n, m;std::cin >> n >> m;assert(1 <= n && 1 <= m && n * m <= kMaxNM);std::vector<int> rc(n + m);for (int i = 0; i < n + m; ++i) {std::cin >> rc[i];assert(0 <= rc[i] && rc[i] < (1 << kDigits));}std::vector a(n, std::vector(m, 0));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {std::cin >> a[i][j];assert(0 <= a[i][j] && a[i][j] < (1 << kDigits));}}std::vector<std::uint32_t> group(n + m, 0); // ビットごと 2 グループに分けるfor (int bit = 0; bit < kDigits; ++bit) {const int criteria = KthBit(a.front().front(), bit);for (int i = 1; i < n; ++i) {const int is_diff = (KthBit(a[i].front(), bit) != criteria ? 1 : 0);for (int j = 1; j < m; ++j) {if (KthBit(a.front()[j], bit) ^ is_diff != KthBit(a[i][j], bit)) {std::cout << "-1\n";return;}}group[i] |= is_diff << bit;}group[n] |= criteria << bit;for (int j = 1; j < m; ++j) {const int is_diff = (KthBit(a.front()[j], bit) != criteria ? 1 : 0);for (int i = 1; i < n; ++i) {if (KthBit(a[i].front(), bit) ^ is_diff != KthBit(a[i][j], bit)) {std::cout << "-1\n";return;}}group[j + n] |= KthBit(a.front()[j], bit) << bit;}}const auto Operation = [&rc, &group](const int bit, const int choice, const std::vector<int>& unknown,const std::vector<int>& or_01, const std::vector<int>& or_12)-> std::tuple<bool, int,std::vector<int>, std::vector<int>, std::vector<int>> {int cost = 0;std::vector<int> next_unknown, next_or_01, next_or_12;for (const int i : or_01) {if (KthBit(group[i], bit) == choice) {++cost;} else {next_or_01.emplace_back(i);}}for (const int i : or_12) {const int bit_of_i = (KthBit(group[i], bit) == choice ? 1 : 0);const int bit_of_rc = KthBit(rc[i], bit);if (bit_of_i > bit_of_rc) {++cost;} else if (bit_of_i == bit_of_rc) {next_or_12.emplace_back(i);}}for (const int i : unknown) {if (KthBit(group[i], bit) == choice) { // 1if (KthBit(rc[i], bit) == 0) {return {false, 0,std::vector<int>{}, std::vector<int>{}, std::vector<int>{}};}++cost;next_or_12.emplace_back(i);} else { // 0(KthBit(rc[i], bit) == 1 ? next_or_01 : next_unknown).emplace_back(i);}}return {true, cost, next_unknown, next_or_01, next_or_12};};const int argmin = std::distance(rc.begin(), std::ranges::min_element(rc));const int need_to_choose = // これより上位のビットは自由に選べないstd::bit_width(static_cast<std::uint32_t>(rc[argmin]));std::uint32_t chosen_group = 0;int current_cost = 0;std::vector<int> unknown(n + m), or_01, or_12;std::iota(unknown.begin(), unknown.end(), 0);for (int bit = kDigits - 1; bit >= need_to_choose; --bit) {const int choice = KthBit(group[argmin], bit) ^ 1;bool is_valid;int added_cost;std::tie(is_valid, added_cost, unknown, or_01, or_12) =Operation(bit, choice, unknown, or_01, or_12);if (!is_valid) {std::cout << "-1\n";return;}chosen_group |= choice << bit;current_cost += added_cost;}int min_cost = (n + m) * 2 + 1;std::uint32_t achievable_group = 0;// 上位からグループを決定するconst auto dfs = [Operation, &min_cost, &achievable_group](auto dfs, const int bit, const std::uint32_t chosen_group,const int current_cost, const std::vector<int> unknown,const std::vector<int> or_01, const std::vector<int> or_12) -> void {if (bit < 0) {if (current_cost < min_cost) {min_cost = current_cost;achievable_group = chosen_group;}return;}std::array<int, 2> next_cost{};std::array<std::vector<int>, 2> next_unknown{}, next_or_01{}, next_or_12{};for (const int choice : std::vector<int>{0, 1}) {std::tie(std::ignore, next_cost[choice],next_unknown[choice], next_or_01[choice], next_or_12[choice]) =Operation(bit, choice, unknown, or_01, or_12);next_cost[choice] += current_cost;}const int early =(next_cost[0] + next_unknown[0].size() + next_or_01[0].size()< next_cost[1] + next_unknown[1].size() + next_or_01[1].size()? 0 : 1);for (const int parity : std::vector<int>{1, 0}) {const int choice = parity ^ early;if (next_cost[choice] >= min_cost) continue;dfs(dfs, bit - 1, chosen_group | (choice << bit), next_cost[choice],next_unknown[choice], next_or_01[choice], next_or_12[choice]);}};dfs(dfs, need_to_choose - 1, chosen_group, current_cost,unknown, or_01, or_12);// 操作列の生成std::vector<std::tuple<char, int, int>> ans;for (int i = 0; i < n; ++i) {const int ans_i =group[i] ^ achievable_group ^ UINT32_C((1 << kDigits) - 1);if (ans_i > rc[i]) {assert(0 <= (ans_i ^ rc[i]) && (ans_i ^ rc[i]) <= rc[i]);ans.emplace_back('r', i, rc[i]);ans.emplace_back('r', i, ans_i ^ rc[i]);} else if (ans_i > 0) {ans.emplace_back('r', i, ans_i);}}for (int j = 0; j < m; ++j) {const int ans_j =group[j + n] ^ achievable_group ^ UINT32_C((1 << kDigits) - 1);if (ans_j > rc[j + n]) {assert(0 <= (ans_j ^ rc[j + n]) && (ans_j ^ rc[j + n]) <= rc[j + n]);ans.emplace_back('c', j, rc[j + n]);ans.emplace_back('c', j, ans_j ^ rc[j + n]);} else if (ans_j > 0) {ans.emplace_back('c', j, ans_j);}}const int k = ans.size();assert(k == min_cost);std::cout << k << '\n';for (const auto& [r_or_c, ij, x] : ans) {std::cout << r_or_c << ' ' << ij + 1 << ' ' << x << std::endl;}}int main() {constexpr int kMaxT = 50000;int t;std::cin >> t;assert(1 <= t && t <= kMaxT);while (t--) Solve();return 0;}