Submission #617217

#TimeUsernameProblemLanguageResultExecution timeMemory
617217ZanitePalinilap (COI16_palinilap)C++17
17 / 100
428 ms524288 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxN = 5005; const int Alph = 26; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll getRand(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} const ll mod = 1049433169; ll madd(ll x, ll y) {x += y; if (x >= mod) x -= mod; return x;} ll mmul(ll x, ll y) {x *= y; x %= mod; return x;} ll modexp(ll x, ll y) { if (!x) return 0; if (!y) return 1; ll t = modexp(x, y >> 1); return mmul(t, mmul(t, ((y & 1ll) ? x : 1))); } ll key; ll kpow[maxN], invkpow[maxN]; ll n; void precomp() { key = getRand(1e5, 2e5); kpow[0] = invkpow[0] = 1; kpow[1] = key, invkpow[1] = modexp(key, mod-2); for (ll i = 1; i <= n; i++) { kpow[i] = mmul(kpow[i-1], kpow[1]); invkpow[i] = mmul(invkpow[i-1], invkpow[1]); } } struct HashString { ll fwd, bwd, len; HashString() {fwd = bwd = len = 0;} HashString(char c) { fwd = bwd = c - 'a'; len = 1; } HashString operator + (const HashString &other) const { HashString ret = HashString(); ret.fwd = madd(fwd, mmul(other.fwd, kpow[len])); ret.bwd = madd(mmul(bwd, kpow[other.len]), other.bwd); ret.len = len + other.len; return ret; } bool isPalindrome() {return (fwd == bwd);} }; string S; ll ans; ll initPalindrome[maxN][maxN], oddPalindrome[maxN]; ll diffChar[maxN][maxN], diagDiff[maxN][maxN]; ll change[maxN][Alph]; void computeInitial() { for (int i = 1; i <= n; i++) { HashString H = HashString(); for (int j = i; j <= n; j++) { H = H + HashString(S[j]); initPalindrome[i][j] = H.isPalindrome(); ans += initPalindrome[i][j]; } } // compute odd palindromes whose center is i for (int c = 1; c <= n; c++) { for (int d = 0; c-d >= 1 && c+d <= n; d++) { oddPalindrome[c] += initPalindrome[c-d][c+d]; } } // compute some sort of prefsum for initPalindrome for (int i = 1; i <= n; i++) { for (int j = n; j >= 1; j--) { initPalindrome[i][j] += initPalindrome[i-1][j] + initPalindrome[i][j+1] - initPalindrome[i-1][j+1]; } } // calculate whether characters at (i, j) are different or not for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { diffChar[i][j] = (S[i] != S[j]); } } // also calculate some sort of diagonal sum for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { diagDiff[i][j] = diagDiff[i-1][j+1] + diffChar[i][j]; //cout << diagDiff[i][j] << ' '; } //cout << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> S; n = S.length(); S = "#" + S; precomp(); computeInitial(); // find for each substring l..r, on which character can it be changed so that it can be a palindrome for (int l = 1; l <= n; l++) { for (int r = l; r <= n; r++) { ll total = diagDiff[r][l] - diagDiff[l-1][r+1]; if (total != 2) continue; //cout << l << ' ' << r << '\n'; // binary search different position int _L = l, _R = r, dpos = -1; while (_L <= _R) { int _M = (_L + _R) >> 1; if (diagDiff[_M][l+r-_M] - diagDiff[l-1][r+1] >= 1) { dpos = _M; _R = _M - 1; } else { _L = _M + 1; } } // insert to change array int dpos2 = l+r-dpos; change[dpos][S[dpos2] - 'a']++; change[dpos2][S[dpos] - 'a']++; //for (ll i = l; i <= r; i++) {cout << S[i];} //cout << '\n'; } } // finally, compute each possible action that we can take ll maxDiff = 0; for (int i = 1; i <= n; i++) { for (int nw = 0; nw < Alph; nw++) { //cout << "change[" << i << "][" << nw << "] = " << change[i][nw] << '\n'; if (nw == S[i] - 'a') continue; // remove all palindromes with that character as a component, except for odd palindromes ll delta = -initPalindrome[i][i] + oddPalindrome[i]; // add all palindromes that will be created delta += change[i][nw]; maxDiff = max(maxDiff, delta); } } cout << ans + maxDiff << '\n'; }

Compilation message (stderr)

palinilap.cpp: In function 'll modexp(ll, ll)':
palinilap.cpp:16:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   16 |  if (!x) return 0; if (!y) return 1;
      |  ^~
palinilap.cpp:16:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   16 |  if (!x) return 0; if (!y) return 1;
      |                    ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...