結果
問題 |
No.1859 ><<<
|
ユーザー |
|
提出日時 | 2025-05-11 20:56:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 216 ms / 2,000 ms |
コード長 | 1,183 bytes |
コンパイル時間 | 627 ms |
コンパイル使用メモリ | 82,160 KB |
実行使用メモリ | 152,828 KB |
最終ジャッジ日時 | 2025-05-11 20:56:51 |
合計ジャッジ時間 | 11,569 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
# https://yukicoder.me/problems/no/1859 B = 15 H = 9007199254740997 def to_h(s): if s == "<": return 1 else: return 2 def main(): N = int(input()) A = list(map(int, input().split())) S = input() array = [] for i in range(2 * N - 1): a = A[i % N] b = A[(i + 1) % N] if a < b: array.append("<") else: array.append(">") r_hash = 0 for i in range(N - 1): r_hash *= B r_hash %= H r_hash += to_h(S[i]) r_hash %= H l_hash = 0 for i in range(N - 1): l_hash *= B l_hash %= H l_hash += to_h(array[i]) l_hash %= H count = 0 index = N - 1 pow_b = pow(B, N - 2, H) while index < len(array) and r_hash != l_hash: i = index - (N - 1) v = (pow_b * to_h(array[i])) % H l_hash -= v l_hash %= H l_hash *= B l_hash %= H l_hash += to_h(array[index]) l_hash %= H index += 1 count += 1 if index == len(array): print(-1) else: print(count) if __name__ == "__main__": main()