#895428 (C++23) No.2505 matriX cOnstRuction

提出ソース

結果

問題	No.2505 matriX cOnstRuction
ユーザー	suisen
提出日時	2023-07-26 21:46:05
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	6,480 bytes
コンパイル時間	1,951 ms
コンパイル使用メモリ	138,780 KB
実行使用メモリ	12,760 KB
最終ジャッジ日時	2023-10-13 22:59:17
合計ジャッジ時間	8,284 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	AC	27 ms 4,352 KB
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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) {  // 1
        if (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;
}

yukicoder

結果

テストケース

ソースコード