結果
問題 | No.2254 Reverse Only |
ユーザー |
![]() |
提出日時 | 2023-03-24 23:37:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 448 ms / 2,000 ms |
コード長 | 1,566 bytes |
コンパイル時間 | 2,268 ms |
コンパイル使用メモリ | 199,416 KB |
最終ジャッジ日時 | 2025-02-11 17:47:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; typedef unsigned long long ull; #include<bits/stdc++.h> using namespace std; const ull B1=1000000007; const ull B2=100000007; bool rolling_hush(vector<ll> &a, vector<ll> &b){ int al=a.size(),bl=b.size(); if(al>bl) return false; ull t1=1,t2=1; rep(i,al){ t1*=B1; t2*=B2; } ull ah=0,bh=0,ch=0,dh=0; rep(i,al){ ah=ah*B1+a[i]; bh=bh*B1+b[i]; ch=ch*B2+a[i]; dh=dh*B2+b[i]; } for(int i=0;i+al<=bl;i++){ if(ah==bh && ch==dh) return true; if(i+al<bl){ bh=bh*B1+b[i+al]-b[i]*t1; dh=dh*B2+b[i+al]-b[i]*t2; } } return false; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int n,k; cin>>n>>k; vector<ll> A(n),B(n); multiset<ll> c,d; bool b=true; rep(i,n){ cin>>A[i]; c.insert(A[i]); } rep(i,n){ cin>>B[i]; if(B[i]!=A[i]) b=false; d.insert(B[i]); } if(b){ cout<<"Yes"<<endl; return 0; } if(k>n || c!=d){ cout<<"No"<<endl; return 0; } if(k==n){ reverse(ALL(B)); b=true; rep(i,n){ if(A[i]!=B[i]) b=false; if(b) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; } } if(k<n-1){ cout<<"Yes"<<endl; return 0; } vector<ll> AA(2*n); rep(i,n){ AA[i]=A[i]; AA[n+i]=A[i]; } if(rolling_hush(B,AA)) cout<<"Yes"<<endl; else{ reverse(ALL(B)); if(rolling_hush(B,AA)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }