結果
問題 |
No.1005 BOT対策
|
ユーザー |
![]() |
提出日時 | 2020-03-06 21:53:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,554 bytes |
コンパイル時間 | 1,625 ms |
コンパイル使用メモリ | 167,344 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-01 20:07:04 |
合計ジャッジ時間 | 2,320 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 WA * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; using pii=pair<int,int>; #define INF LONG_MAX #define MOD 1000000007 #define rng(a) a.begin(),a.end() #define rrng(a) a.end(),a.begin() #define rep(i,N) for(int i=0;i<N;i++) vector<int> RH(string S,string T){ int SN=S.size(); int TN=T.size(); int_fast64_t b=9973; vector<int_fast64_t>mod={1000000007LL,1000000009LL,1000000021LL}; int M=mod.size(); vector<int_fast64_t>s(M,0); vector<int_fast64_t>t(M,0); vector<int_fast64_t>a(M,1); for(int i=0;i<TN;i++){ for(int j=0;j<M;j++){ a[j]=(a[j]*b)%mod[j]; } } for(int i=0;i<TN;i++){ for(int j=0;j<M;j++){ s[j]=((s[j]*b)%mod[j]+S[i])%mod[j]; } } for(int i=0;i<TN;i++){ for(int j=0;j<M;j++){ t[j]=((t[j]*b)%mod[j]+T[i])%mod[j]; } } vector<int>res; bool ok=true; for(int i=0;i<M;i++)if(s[i]!=t[i])ok=false; if(ok)res.push_back(0); for(int i=0;i+TN<SN;i++){ ok=true; for(int j=0;j<M;j++){ s[j]=((s[j]*b)%mod[j]-(S[i]*a[j])%mod[j])%mod[j]; if(s[j]<0)s[j]+=mod[j]; s[j]=(s[j]+S[i+TN])%mod[j]; if(s[j]!=t[j])ok=false; } if(ok)res.push_back(i+1); } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); string S,T; cin>>S>>T; auto rh=RH(S,T); if(T.size()==1&&rh.size()!=0){ cout<<-1<<endl; return 0; } ll c=0; for(int i=0;i<rh.size();i++){ c++; if(i+1<rh.size()){ if(rh[i]+T.size()-1>rh[i+1])i++; } } cout<<c<<endl; return 0; }