제출 #71865

#제출 시각아이디문제언어결과실행 시간메모리
71865evpipis회문 (APIO14_palindrome)C++14
100 / 100
973 ms61544 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back typedef long long ll; typedef pair<int, int> ii; const int len = 3e5+5, mod = 1e9+7, base = 57; int suf[len], has1[len], has2[len], po[len], lim[len], n, lef[len], rig[len]; int tmp[len], ran[len], cnt[len]; char str[len]; vector<int> vec[len]; vector<ii> st; set<int> mys; inline int add(int a, int b){ a += b; if (a >= mod) a -= mod; return a; } inline int sub(int a, int b){ a -= b; if (a < 0) a += mod; return a; } int mul(int a, int b){ return (a*1LL*b)%mod; } inline int val1(int l, int r){ l++, r++; return sub(has1[r], mul(has1[l-1], po[r-l+1])); } inline int val2(int l, int r){ return (sub(has2[l], mul(has2[r+1], po[r-l+1]))); } int lcp(int a, int b){ int l = 1, r = n-1-max(a, b)+1, ans = 0; while (l <= r){ int mid = (l+r)/2; if (val1(a, a+mid-1) == val1(b, b+mid-1)) ans = mid, l = mid+1; else r = mid-1; } return ans; } int bs(int i, int t){ int l = 1, r = min(n-i-t, i+1), ans = 0; while (l <= r){ int mid = (l+r)/2; if (val1(i-mid+1, i+t+mid-1) == val2(i-mid+1, i+t+mid-1)) ans = 2*mid - (1-t), l = mid+1; else r = mid-1; } return ans; } void radix(int k){ for (int i = 0; i <= max(n, 300); i++) cnt[i] = 0; for (int i = 0; i < n; i++) cnt[(suf[i]+k<n?ran[suf[i]+k]:0)+1]++; for (int i = 1; i <= max(n, 300); i++) cnt[i] += cnt[i-1]; for (int i = 0; i < n; i++) tmp[cnt[(suf[i]+k<n?ran[suf[i]+k]:0)]++] = suf[i]; for (int i = 0; i < n; i++) suf[i] = tmp[i]; } int main(){ scanf("%s", &str); n = strlen(str); str[n++] = 0; po[0] = 1; for (int i = 1; i <= n; i++) po[i] = mul(po[i-1], base); for (int i = 1; i <= n; i++) has1[i] = add(mul(has1[i-1], base), str[i-1]-'a'); for (int i = n-1; i >= 0; i--) has2[i] = add(mul(has2[i+1], base), str[i]-'a'); for (int i = 0; i < n; i++) suf[i] = i; //sort(suf, suf+n, comp); // suffix array before :( for (int i = 0; i < n; i++) ran[i] = str[i]; for (int k = 1; k <= n; k*=2){ radix(k); radix(0); int ptr = -1; for (int i = 0; i < n; i++){ if (i == 0 || ran[suf[i]] != ran[suf[i-1]] || ran[suf[i]+k] != ran[suf[i-1]+k]) tmp[suf[i]] = ++ptr; else tmp[suf[i]] = ptr; } for (int i = 0; i < n; i++) ran[i] = tmp[i]; if (ptr == n-1) break; } for (int i = 0; i < n; i++) lim[i] = -1; for (int i = 0; i < n-1; i++) lim[suf[i]] = lcp(suf[i], suf[i+1]); //for (int i = 0; i < n; i++) // printf("%d ", suf[i]); //printf("\n"); ll ans = 0; for (int i = 0; i < n; i++){ int temp = bs(i, 0); vec[i-temp/2].pb(temp); ans = max(ans, (ll)temp); //printf("i = %d, mx0 = %d\n", i, temp); temp = bs(i, 1); vec[i-temp/2+1].pb(temp); ans = max(ans, (ll)temp); //printf("i = %d, mx1 = %d\n", i, temp); } int k = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < vec[i].size(); j++) mys.insert(vec[i][j]-k); set<int>::iterator it = mys.upper_bound(lim[i]-k); if (lim[i] != -1 && it != mys.begin()){ it = prev(it); lim[i] = *it + k; } else lim[i] = 0; k-=2; } //for (int i = 0; i < n-1; i++) // printf("%d ", lim[suf[i]]); //printf("\n"); st.pb(mp(-1, -1)); for (int i = 0; i < n-1; i++){ while (lim[suf[i]] <= st.back().fi) st.pop_back(); lef[i] = st.back().se; st.pb(mp(lim[suf[i]], i)); } st.clear(), st.pb(mp(-1, n-1)); for (int i = n-2; i >= 0; i--){ while (lim[suf[i]] <= st.back().fi) st.pop_back(); rig[i] = st.back().se; st.pb(mp(lim[suf[i]], i)); } for (int i = 0; i < n-1; i++) ans = max(ans, lim[suf[i]] * 1LL * (rig[i]-lef[i])); printf("%lld\n", ans); return 0; }

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

palindrome.cpp: In function 'int main()':
palindrome.cpp:85:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
     scanf("%s", &str);
                 ~~~~^
palindrome.cpp:147:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vec[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~
palindrome.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", &str);
     ~~~~~^~~~~~~~~~~~
#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...