#611381 (C++17) No.1369 交換門松列・竹

提出ソース

結果

問題	No.1369 交換門松列・竹
ユーザー	Haar
提出日時	2021-01-29 22:31:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	7,046 bytes
コンパイル時間	2,437 ms
コンパイル使用メモリ	217,472 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-27 08:49:09
合計ジャッジ時間	3,089 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	WA	-
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	4 ms 6,940 KB
testcase_14	WA	-
testcase_15	AC	7 ms 6,940 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	6 ms 6,940 KB
testcase_20	AC	7 ms 6,940 KB
testcase_21	AC	6 ms 6,940 KB
testcase_22	AC	6 ms 6,944 KB
testcase_23	WA	-
testcase_24	AC	7 ms 6,944 KB
testcase_25	AC	5 ms 6,940 KB
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	5 ms 6,940 KB
testcase_29	AC	5 ms 6,944 KB
testcase_30	AC	6 ms 6,944 KB
testcase_31	AC	6 ms 6,940 KB
testcase_32	WA	-
testcase_33	AC	5 ms 6,940 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()){
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1){
    return std::vector<T>(a[N - I], value);
  }else{
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}

std::string YesNo(bool value){return value ? "Yes" : "No";}
std::string YESNO(bool value){return value ? "YES" : "NO";}
std::string yesno(bool value){return value ? "yes" : "no";}

template <typename T>
void putl(const T &value){
  std::cout << value << "\n";
}

template <typename Head, typename ... Tail>
void putl(const Head head, const Tail &... tail){
  std::cout << head << " ";
  putl(tail ...);
}

namespace haar_lib {}

namespace haar_lib {
  template <typename Container>
  auto run_length_encoding(const Container &v){
    using T = typename Container::value_type;

    std::vector<std::pair<T, int64_t>> ret;

    for(auto &&x : v){
      if(ret.empty()) ret.emplace_back(x, 1);
      else if(ret.back().first == x) ++ret.back().second;
      else ret.emplace_back(x, 1);
    }

    return ret;
  }
}


namespace solver {
  using namespace haar_lib;

  constexpr int m1000000007 = 1000000007;
  constexpr int m998244353 = 998244353;

  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  bool is_kadomatsu(int64_t a, int64_t b, int64_t c){
    if(a != b and b != c and c != a){
      if(std::min({a, b, c}) == b or std::max({a, b, c}) == b){
        return true;
      }
    }
    return false;
  }

  void solve(){
    int T; std::cin >> T;
    while(T--){
      int N; std::cin >> N;
      std::vector<int> A(N); std::cin >> A;


      std::vector<bool> kadomatsu(N - 2);
      for(int i = 0; i < N - 2; ++i){
        kadomatsu[i] = is_kadomatsu(A[i], A[i + 1], A[i + 2]);
      }

      dump(kadomatsu);

      auto r = run_length_encoding(kadomatsu);

      dump(r);

      std::vector<std::pair<int, int>> enum_false;
      int pos = 0;
      for(auto [p, c] : r){
        if(p == false){
          enum_false.emplace_back(pos, c);
        }
        pos += c;
      }

      dump(enum_false);

      if(enum_false.size() >= 3){
        std::cout << YesNo(false) << "\n";
        continue;
      }

      if(enum_false.size() == 2){
        if(enum_false[0].second < 10 or enum_false[1].second < 10){
          bool res =
            [&](){
              int s1 = enum_false[0].first, t1 = s1 + enum_false[0].second;
              int s2 = enum_false[1].first, t2 = s2 + enum_false[1].second;
              for(int i = std::max(s1 - 5, 0); i < std::min(t1 + 5, N); ++i){
                for(int j = std::max(s2 - 5, 0); j < std::min(t2 + 5, N); ++j){
                  if(i != j and A[i] != A[j]){
                    bool ok = true;
                    std::swap(A[i], A[j]);

                    for(int k = std::max(s1 - 5, 0); k < std::min(t1 + 5, N - 2); ++k){
                      if(not is_kadomatsu(A[k], A[k + 1], A[k + 2])){
                        ok = false;
                        break;
                      }
                    }

                    for(int k = std::max(s2 - 5, 0); k < std::min(t2 + 5, N - 2); ++k){
                      if(not is_kadomatsu(A[k], A[k + 1], A[k + 2])){
                        ok = false;
                        break;
                      }
                    }


                    std::swap(A[i], A[j]);
                    if(ok){
                      std::cout << YesNo(true) << "\n";
                      return true;
                    }
                  }
                }
              }
              return false;
            }();
          if(res) continue;
        }


        if(enum_false[1].first - enum_false[0].first < 20){
          bool res =
            [&](){
              int s = enum_false[0].first;
              int t = s + 50;
              for(int i = std::max(s - 5, 0); i < std::min(t + 5, N); ++i){
                for(int j = 0; j < N; ++j){
                  if(i != j and A[i] != A[j]){
                    bool ok = true;
                    std::swap(A[i], A[j]);

                    for(int k = std::max(s - 5, 0); k < std::min(t + 5, N - 2); ++k){
                      if(not is_kadomatsu(A[k], A[k + 1], A[k + 2])){
                        ok = false;
                        break;
                      }
                    }

                    std::swap(A[i], A[j]);
                    if(ok){
                      std::cout << YesNo(true) << "\n";
                      return true;
                    }
                  }
                }
              }
              return false;
            }();
          if(res) continue;
        }
        
      }

      if(enum_false.size() == 1){
        if(enum_false[0].second > 20){
          std::cout << YesNo(false) << "\n";
          continue;
        }

        bool res =
          [&](){
            int s = enum_false[0].first;
            int t = s + enum_false[0].second;
            for(int i = std::max(s - 5, 0); i < std::min(t + 5, N); ++i){
              for(int j = 0; j < N; ++j){
                if(i != j and A[i] != A[j]){
                  bool ok = true;
                  std::swap(A[i], A[j]);

                  for(int k = std::max(s - 5, 0); k < std::min(t + 5, N - 2); ++k){
                    if(not is_kadomatsu(A[k], A[k + 1], A[k + 2])){
                      ok = false;
                      break;
                    }
                  }

                  std::swap(A[i], A[j]);
                  if(ok){
                    std::cout << YesNo(true) << "\n";
                    return true;
                  }
                }
              }
            }
            return false;
          }();
        if(res) continue;






      }

      std::cout << YesNo(false) << "\n";
    }
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
      std::cout << std::flush;
      std::cerr << std::flush;
    }catch(const std::istream::failure &e){
      break;
    }catch(...){
      break;
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード