結果
問題 | No.958 たぷりすたべる (回文) |
ユーザー |
![]() |
提出日時 | 2019-12-21 00:10:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 1,111 bytes |
コンパイル時間 | 771 ms |
コンパイル使用メモリ | 77,532 KB |
実行使用メモリ | 8,432 KB |
最終ジャッジ日時 | 2024-07-18 03:54:25 |
合計ジャッジ時間 | 4,018 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 53 |
ソースコード
#include <cstdio> #include <algorithm> #include <vector> #include <functional> #include <iterator> #include <iostream> #include <string> using namespace std; namespace{ typedef long long LL; template <class RIter, class Comparer = std::equal_to<typename std::iterator_traits<RIter>::value_type> > std::vector<int> manacher(RIter s, RIter en, const Comparer &eqcomp = Comparer()){ int i = 0, j = 0; int n = std::distance(s, en); std::vector<int> res(n); while (i < n){ while(i - j >= 0 && i + j < n && eqcomp(s[i - j], s[i + j])){ ++j; } res[i] = j; int k = 1; while(i - k >= 0 && i + k < n && k + res[i - k] < j){ res[i + k] = res[i - k]; ++k; } i += k; j -= k; } return res; } void main2(){ ios::sync_with_stdio(false); cin.tie(0); int n, q; LL k; string s; cin >> n >> k >> q >> s; string u = s + s + s + s + s; vector<int> mn = manacher(u.begin(), u.end()); for(; q--; ){ LL a; cin >> a; --a; int b = a % n; LL z = mn[b + 2 * n]; if(z > n){ z = k * n; } z = min({z, a + 1, k * n - a}); cout << (z * 2 - 1) << '\n'; } } } int main(){ main2(); }