Submission #388095

#TimeUsernameProblemLanguageResultExecution timeMemory
388095KeshiPalindromes (APIO14_palindrome)C++17
0 / 100
199 ms14272 KiB
//In the name of God #include <bits/stdc++.h> using namespace std; typedef int ll; typedef pair<ll, ll> pll; const ll maxn = 2e5 + 100; const ll mod = 1e9 + 7; const ll inf = 1e18; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() ll n, p[maxn], rnk[maxn], r2[maxn], lcp[maxn]; string s; ll h; vector<ll> vec[maxn]; bool cmp(ll i, ll j){ if(rnk[i] < rnk[j]) return 1; if(rnk[i] > rnk[j]) return 0; i += h; j += h; if(i >= n) i -= n; if(j >= n) j -= n; return (rnk[i] < rnk[j]); } int main(){ fast_io; cin >> s; s += '#'; n = Sz(s); for(ll i = 0; i < n; i++){ rnk[i] = ll(s[i] - 'a'); p[i] = i; } h = 0; sort(p, p + n, cmp); r2[p[0]] = 0; for(ll i = 1; i < n; i++){ r2[p[i]] = r2[p[i - 1]]; if(cmp(p[i - 1], p[i])) r2[p[i]]++; } for(ll i = 0; i < n; i++){ rnk[i] = r2[i]; } h = 1; while(h < n){ sort(p, p + n, cmp); r2[p[0]] = 0; for(ll i = 1; i < n; i++){ r2[p[i]] = r2[p[i - 1]]; if(cmp(p[i - 1], p[i])) r2[p[i]]++; } for(ll i = 0; i < n; i++){ rnk[i] = r2[i]; } h <<= 1; } for(ll i = 0; i < n; i++){ cout << p[i] << " " << rnk[p[i]] << "\n"; } for(ll i = 0, k = 0; i < n; i++){ if(rnk[i] == n - 1){ k = 0; continue; } ll j = p[rnk[i] + 1]; while(i + k < n && j + k < n && s[i + k] == s[j + k]) k++; lcp[rnk[i]] = k; if(k) k--; } for(ll i = 0; i < n; i++){ cout << lcp[i] << "\n"; } n--; vector<int> d1(n); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) { k++; } d1[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } vector<int> d2(n); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1); while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) { k++; } d2[i] = k--; if (i + k > r) { l = i - k - 1; r = i + k; } } set<ll> st; ll cnt = 0; for(ll i = n; i--;){ for(ll j : vec[i]){ st.erase(j); } st.insert(i); vec[i - d1[i]].pb(i); auto it = st.rbegin(); while(it != st.rend()){ if((*it - i) * 2 + 1 <= lcp[rnk[i] - 1]) break; cnt++; it++; } } cout << cnt; return 0; }

Compilation message (stderr)

palindrome.cpp:10:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const ll inf = 1e18;
      |                ^~~~
#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...