結果
問題 | No.1369 交換門松列・竹 |
ユーザー |
|
提出日時 | 2021-01-29 22:06:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,429 bytes |
コンパイル時間 | 808 ms |
コンパイル使用メモリ | 79,448 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-27 08:19:02 |
合計ジャッジ時間 | 2,383 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
コンパイルメッセージ
main.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 12 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;int T,N;int A[50505];bool f(int id){int x=A[id],y=A[id+1],z=A[id+2];return(x<y&&y>z||x>y&&y<z)&&x!=z;}main(){cin>>T;for(;T--;){cin>>N;for(int i=0;i<N;i++)cin>>A[i];vector<int>X;int out=0;for(int i=0;i+3<=N;i++)if(!f(i)){out++;X.push_back(i);X.push_back(i+1);X.push_back(i+2);}sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());bool fn=false;if(X.size()<=7){for(int i:X)for(int j=0;j<N;j++)if(i!=j){vector<int>ch;for(int k=-2;k<=2;k++){if(i+k>=0&&i+k+3<=N)ch.push_back(i+k);if(j+k>=0&&j+k+3<=N)ch.push_back(j+k);}sort(ch.begin(),ch.end());ch.erase(unique(ch.begin(),ch.end()),ch.end());int now=out;for(int k:ch)now-=!f(k);swap(A[i],A[j]);for(int k:ch)now+=!f(k);if(now==0)fn=true;swap(A[i],A[j]);}}else if(X.size()<=100){for(int i:X)for(int j:X)if(i<j){vector<int>ch;for(int k=-2;k<=2;k++){if(i+k>=0&&i+k+3<=N)ch.push_back(i+k);if(j+k>=0&&j+k+3<=N)ch.push_back(j+k);}sort(ch.begin(),ch.end());ch.erase(unique(ch.begin(),ch.end()),ch.end());int now=out;for(int k:ch)now-=!f(k);swap(A[i],A[j]);for(int k:ch)now+=!f(k);if(now==0)fn=true;swap(A[i],A[j]);}}cout<<(fn?"Yes":"No")<<endl;}}