제출 #670818

#제출 시각아이디문제언어결과실행 시간메모리
670818fatemetmhr회문 (APIO14_palindrome)C++17
100 / 100
965 ms107252 KiB
// ~ Be Name Khoda ~ #include <bits/stdc++.h> #pragma GCC optimize ("Ofast") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; #define all(x) x.begin(), x.end() #define pb push_back #define fi first #define se second const int maxn5 = 3e5 + 10; const int lg = 19; const ll inf = 1e18; const int al = 200; int rnk[lg][maxn5], a[maxn5], lef[maxn5], rig[maxn5]; int val[maxn5], mn[maxn5], lcp[maxn5], rev[maxn5]; int cmpid, lenlen, cmpsz, z[2][maxn5]; set <int> av[2]; vector <int> srt[maxn5]; vector <pair<int, int>> ed; vector <pair<int, pair<int, int>>> have; vector <pair<pair<int, int>, int>> req; inline int get_lcp(int v, int u){ int ans = 0; for(int i = lg - 1; i >= 0; i--) if(rnk[i][u] == rnk[i][v]){ u += (1 << i); v += (1 << i); ans += (1 << i); } return ans; } inline void fix2(int& a){ if(a < 0) a += cmpsz; if(a >= cmpsz) a -= cmpsz; } inline int fix(int a){ if(a >= cmpsz) a -= cmpsz; return a; } inline bool cmp(int i, int j){ return rnk[cmpid][i] < rnk[cmpid][j] || (rnk[cmpid][i] == rnk[cmpid][j] && rnk[cmpid][fix(i + lenlen)] < rnk[cmpid][fix(j + lenlen)]); } inline void sort1(int n){ for(int i = 0; i < max(n, al); i++) srt[i].clear(); for(int i = 0; i < n; i++) srt[rnk[cmpid][fix(i + lenlen)]].pb(i); int pt = 0; for(int i = 0; i < max(n, al); i++) for(auto u : srt[i]) a[pt++] = u; } inline void sort(){ int n = cmpsz; for(int i = 0; i < n; i++) srt[rnk[cmpid][a[i]]].pb(a[i]); int pt = 0; for(int i = 0; i < max(n, al); i++){ for(auto u : srt[i]) a[pt++] = u; srt[i].clear(); } } inline void build_sf(string s){ s.pb('#'); int n = cmpsz = s.size(); for(int i = 0; i < n; i++){ rnk[0][i] = int(s[i]); srt[rnk[0][i]].pb(i); } int pt = 0; for(int i = 0; i < al; i++) for(auto u : srt[i]) a[pt++] = u; for(int i = 0; i < al; i++) srt[i].clear(); for(int j = 1; j < lg; j++){ cmpid = j - 1; lenlen = (1 << cmpid) % n; for(int i = 0; i < n; i++) fix2(a[i] = a[i] - lenlen); sort(); rnk[j][a[0]] = 0; for(int i = 1; i < n; i++){ rnk[j][a[i]] = rnk[j][a[i - 1]] + cmp(a[i - 1], a[i]); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int n = s.size(); build_sf(s); for(int i = 0; i < n; i++) a[i] = a[i + 1]; for(int i = 1; i < n; i++){ lcp[i] = get_lcp(a[i - 1], a[i]); ed.pb({lcp[i], i}); } ll ans = 0; //cout << t << endl; for(int i = 0; i < n; i++){ //cout << a[i] << ' '; rev[a[i]] = i; lef[i] = rig[i] = i; } int l = 0, r = 0; for(int i = 0; i < n; i++){ if(i){ if(r >= i) z[1][i] = min(r - i + 1, z[1][r + l - i + 1]); while(z[1][i] + i < n && i - z[1][i] - 1 >= 0 && s[i + z[1][i]] == s[i - z[1][i] - 1]) z[1][i]++; have.pb({i - z[1][i], {1, i - 1}}); ans = max(ans, z[1][i] * 2LL); if(i + z[1][i] - 1 > r){ r = i + z[1][i] - 1; l = i - z[1][i]; } } if(r >= i) z[0][i] = min(r - i + 1, z[0][r + l - i]); while(z[0][i] + i < n && i - z[0][i] >= 0 && s[i + z[0][i]] == s[i - z[0][i]]) z[0][i]++; have.pb({i - z[0][i] + 1, {0, i}}); if(i + z[0][i] - 1 > r){ r = i + z[0][i] - 1; l = i - z[0][i] + 1; } ans = max(ans, z[0][i] * 2LL - 1); } sort(all(ed)); while(ed.size()){ int id = ed.back().se, len = ed.back().fi; ed.pop_back(); int l, r; lef[rig[id]] = l = lef[id - 1]; rig[lef[id - 1]] = r = rig[id]; req.pb({{a[l], len}, r - l + 1}); } sort(all(req)); sort(all(have)); int ind = 0; //cout << "having " << ans << endl; for(auto [b, val] : req){ int l = b.fi, len = b.se; //cout << "A request of " << l << ' ' << len << ' ' << val << endl; while(ind < have.size() && have[ind].fi <= l){ av[have[ind].se.fi].insert(have[ind].se.se); //cout << "adding " << have[ind].fi << ' ' << have[ind].se.fi << ' ' << have[ind].se.se << endl; ind++; } int klen = len / 2; int slen = klen + len % 2; auto it = av[0].upper_bound(l + slen - 1); if(av[0].size() && it != av[0].begin()){ it--; ans = max(ans, ll(val) * (((*it) - l) * 2 + 1)); //cout << "well fard " << (*it) << ' ' << ans << endl; } it = av[1].upper_bound(l + klen - 1); if(av[1].size() && it != av[1].begin()){ it--; ans = max(ans, ll(val) * ((*it) - l + 1) * 2); //cout << "well zoj " << (*it) << ' ' << ans << endl; } } cout << ans << endl; } /* Why so fast...? Hold on... Hold your breath... Need anything else? Nein, Kein Problem... Das Leben war schon immer so grausam :) */

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:173:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         while(ind < have.size() && have[ind].fi <= l){
      |               ~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...