結果
問題 |
No.1859 ><<<
|
ユーザー |
|
提出日時 | 2022-03-23 10:42:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,978 bytes |
コンパイル時間 | 1,756 ms |
コンパイル使用メモリ | 172,612 KB |
実行使用メモリ | 14,580 KB |
最終ジャッジ日時 | 2024-10-11 08:11:42 |
合計ジャッジ時間 | 5,436 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i = 0; i < n; ++i) #define REP(i, x, n) for(int i = (x); i < n; ++i) #define rrep(i, n) for(int i = n - 1; i >= 0; --i) #define RREP(i, x, n) for(int i = n - 1; i >= (x); --i) #define all(x) x.begin(), x.end() using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>; using vb = vector<bool>; using vvb = vector<vb>; using P = pair<int, int>; using Pll = pair<ll, ll>; using vp = vector<P>; using vvp = vector<vp>; template <class T> bool chmax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, const T &b) { if(b < a) { a = b; return 1; } return 0; } template <typename T> vector<int> Zalgorithm(vector<T> S) { int n = S.size(); vector<int> arr(n); arr[0] = n; int i = 1, j = 0; while(i < n) { while(i + j < n && S[j] == S[i + j]) ++j; arr[i] = j; if(j == 0) { ++i; continue; } int k = 1; while(i + k < n && k + arr[k] < j) { arr[i + k] = arr[k]; ++k; } i += k; j -= k; } return arr; } void solve() { int n; cin >> n; vi a(n); rep(i, n) cin >> a[i]; string s; cin >> s; string t; rep(i, 2 * n - 2) t += (a[(i) % n] < a[(i + 1) % n] ? '<' : '>'); vector<char> u; for(char &e : s) u.push_back(e); for(char &e : t) u.push_back(e); for(char &e : t) u.push_back(e); --n; auto z = Zalgorithm(u); REP(i, n, 3 * n) { if(z[i] >= n) { cout << i - n << endl; return; } } cout << -1 << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; while(t--) solve(); return 0; }