結果
問題 |
No.1859 ><<<
|
ユーザー |
|
提出日時 | 2022-03-16 00:18:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,160 bytes |
コンパイル時間 | 1,832 ms |
コンパイル使用メモリ | 170,560 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-09-22 16:51:59 |
合計ジャッジ時間 | 6,578 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include<bits/stdc++.h> using namespace std; long long modpow(long long a,int n,long long mod){ long long ret=1,t=a; for(int i=0;i<31;i++){ if(n>>i&1)ret=ret*t%mod; t=t*t%mod; } return ret; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; vector<int>A(N); for(int &i:A)cin>>i; string S; cin>>S; vector<int>F(N*2+1); for(int i=0;i<=N*2;i++){ F[i]=A[i%N]>A[(i+1)%N]; } const int mod[4]={1000000007,1000000009,998244853,998244353}; array<long long,4>inori={0ll,0ll,0ll,0ll},awase=inori,modkese; for(int i=0;i<4;i++)modkese[i]=modpow(2,N-1,mod[i]); for(int i=0;i<N-1;i++){ for(int j=0;j<4;j++){ inori[j]=(inori[j]*2+(S[i]=='>'?1:0))%mod[j]; } } for(int i=0;i<N-1;i++){ for(int j=0;j<4;j++){ awase[j]=(awase[j]*2+F[i])%mod[j]; } } for(int i=N-1;i<N*2;i++){ if(inori==awase){ cout<<i-N+1<<'\n'; return 0; } for(int j=0;j<4;j++){ awase[j]=(awase[j]*2+F[i])%mod[j]; if(F[i-N+1])awase[j]=(awase[j]-modkese[j]+mod[j])%mod[j]; } } if(inori==awase){ cout<<N-1<<'\n'; return 0; } cout<<"-1\n"; }