結果

問題 No.1369 交換門松列・竹
ユーザー HaarHaar
提出日時 2021-01-29 22:31:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,046 bytes
コンパイル時間 2,231 ms
コンパイル使用メモリ 214,508 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-09 16:02:12
合計ジャッジ時間 3,735 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 WA -
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 4 ms
4,376 KB
testcase_14 WA -
testcase_15 AC 6 ms
4,380 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 6 ms
4,376 KB
testcase_20 AC 7 ms
4,376 KB
testcase_21 AC 6 ms
4,376 KB
testcase_22 AC 6 ms
4,376 KB
testcase_23 WA -
testcase_24 AC 6 ms
4,380 KB
testcase_25 AC 5 ms
4,376 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 5 ms
4,376 KB
testcase_29 AC 5 ms
4,376 KB
testcase_30 AC 6 ms
4,376 KB
testcase_31 AC 6 ms
4,376 KB
testcase_32 WA -
testcase_33 AC 5 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0