tests/next_matching.test.cpp

View this file on GitHub
Last update: 2025-01-25 08:45:50+09:00
Problem: https://atcoder.jp/contests/abc236/tasks/abc236_d

Depends on

Code

// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc236/tasks/abc236_d
// competitive-verifier: IGNORE

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include "tools/chmax.hpp"
#include "tools/next_matching.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N;
  std::cin >> N;

  auto A = std::vector(2 * N, std::vector<ll>(2 * N));
  for (ll i = 0; i < 2 * N; ++i) {
    for (ll j = i + 1; j < 2 * N; ++j) {
      std::cin >> A[i][j];
      A[j][i] = A[i][j];
    }
  }

  std::vector<ll> pattern(2 * N);
  std::iota(pattern.begin(), pattern.end(), 0);

  ll answer = std::numeric_limits<int>::min();
  do {
    ll possible_answer = 0;
    for (ll i = 0; i < 2 * N; i += 2) {
      possible_answer ^= A[pattern[i]][pattern[i + 1]];
    }
    tools::chmax(answer, possible_answer);
  } while (tools::next_matching(pattern.begin(), pattern.end()));

  std::cout << answer << '\n';
  return 0;
}

#line 1 "tests/next_matching.test.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc236/tasks/abc236_d
// competitive-verifier: IGNORE

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#line 1 "tools/chmax.hpp"



#include <type_traits>
#include <utility>

namespace tools {

  template <typename M, typename N>
  bool chmax(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(lhs, rhs);
    } else {
      updated = lhs < rhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/next_matching.hpp"



#include <iterator>
#include <cassert>
#include <algorithm>

namespace tools {
  template <typename RandomAccessIterator>
  bool next_matching(RandomAccessIterator begin, RandomAccessIterator end) {
    const auto N = ::std::distance(begin, end);
    // assert(::tools::mex(begin, end) == N);
    if (N <= 2) return false;

    auto l = (N - 2) / 2 * 2;
    for (; l > 0 && begin[l - 1] > begin[l + 1]; l -= 2);
    ::std::sort(::std::next(begin, l), ::std::prev(end, N % 2));

    if (l == 0) {
      if (N % 2 == 0) return false;
      if (begin[N - 1] == 0) {
        ::std::rotate(begin, ::std::prev(end), end);
        return false;
      }
      ::std::iter_swap(::std::next(begin, begin[N - 1] - 1), ::std::prev(end));
      return true;
    }

    ::std::iter_swap(::std::next(begin, l - 1), ::std::upper_bound(::std::next(begin, l), ::std::prev(end, N % 2), begin[l - 1]));
    return true;
  }
}


#line 10 "tests/next_matching.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N;
  std::cin >> N;

  auto A = std::vector(2 * N, std::vector<ll>(2 * N));
  for (ll i = 0; i < 2 * N; ++i) {
    for (ll j = i + 1; j < 2 * N; ++j) {
      std::cin >> A[i][j];
      A[j][i] = A[i][j];
    }
  }

  std::vector<ll> pattern(2 * N);
  std::iota(pattern.begin(), pattern.end(), 0);

  ll answer = std::numeric_limits<int>::min();
  do {
    ll possible_answer = 0;
    for (ll i = 0; i < 2 * N; i += 2) {
      possible_answer ^= A[pattern[i]][pattern[i + 1]];
    }
    tools::chmax(answer, possible_answer);
  } while (tools::next_matching(pattern.begin(), pattern.end()));

  std::cout << answer << '\n';
  return 0;
}