結果
| 問題 |
No.1369 交換門松列・竹
|
| コンテスト | |
| ユーザー |
 Haar
|
| 提出日時 | 2021-01-29 22:31:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,046 bytes |
| コンパイル時間 | 2,241 ms |
| コンパイル使用メモリ | 208,712 KB |
| 最終ジャッジ日時 | 2025-01-18 09:31:41 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 24 WA * 9 |
ソースコード
#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;
}