結果
問題 |
No.1859 ><<<
|
ユーザー |
|
提出日時 | 2022-03-16 00:06:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,124 bytes |
コンパイル時間 | 1,639 ms |
コンパイル使用メモリ | 171,040 KB |
実行使用メモリ | 7,184 KB |
最終ジャッジ日時 | 2024-09-22 16:38:23 |
合計ジャッジ時間 | 8,062 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 WA * 26 |
ソースコード
#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); 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-2;i++){ for(int j=0;j<4;j++){ awase[j]=(awase[j]*2+F[i])%mod[j]; } } for(int i=N-2;i<N*2;i++){ for(int j=0;j<4;j++){ awase[j]=(awase[j]*2+F[i])%mod[j]; } if(inori==awase){ cout<<i-N+2<<'\n'; return 0; } for(int j=0;j<4;j++){ if(F[i-N+1])awase[j]=(awase[j]-modkese[j]+mod[j])%mod[j]; } } cout<<"-1\n"; }