結果
問題 | 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; } }