Submission #1021794

#TimeUsernameProblemLanguageResultExecution timeMemory
1021794PVSekharPalinilap (COI16_palinilap)C++17
0 / 100
4 ms2104 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int MOD = 1e9 + 7; const int N = 2e5 + 2; const int P = 31; string s, t = "{"; ll n, pref[N], suff[N], p_pow[N], diff[N]; int palin[N], c_ind, c_val; void comp_pref() { pref[0] = suff[0] = 0; for (int i = 1; i <= n; i++) { pref[i] = (pref[i - 1] + ((t[i - 1] - 'a' + 1) * p_pow[i - 1] % MOD)) % MOD; suff[i] = (suff[i - 1] + ((t[n - i] - 'a' + 1) * p_pow[i - 1] % MOD)) % MOD; } } bool check_palin(int i, int len, int change) { ll val1 = MOD + pref[i + len] - pref[i - len + 1], p1 = i - len + 1, val2 = MOD + suff[n - i + len - 1] - suff[n - i - len], p2 = n - i - len; if (change) { val1 = MOD + val1 + (c_val * p_pow[c_ind] % MOD); val2 = MOD + val2 + (c_val * p_pow[n - c_ind - 1] % MOD); } val1 %= MOD, val2 %= MOD; if (p1 > p2) val2 *= p_pow[p1 - p2], val2 %= MOD; else val1 *= p_pow[p2 - p1], val1 %= MOD; if (val1 == val2) return true; return false; } void solve() { p_pow[0] = 1; for (int i = 1; i < N; i++) p_pow[i] = p_pow[i-1] * P % MOD; ll ans = 0, m_val = 0; cin >> s; for (char x : s) t += x, t += '{'; n = t.length(); for (int i = 0; i <= n; i++) diff[i] = 0; comp_pref(); vector<vector<ll>> val(n, vector<ll> (26, 0)), p_cent(n); int l = 0, r = 0, mid; for (int i = 0; i < n; i++) { l = 1, r = n+1; while (r - l > 1) { mid = (l + r) / 2; if (i + mid - 1 < n && i - mid + 1 >= 0 && check_palin(i, mid, 0)) { l = mid; } else { r = mid; } } palin[i] = l; if (i - l >= 0 && i + l < n) p_cent[i - l].push_back(i), p_cent[i + l].push_back(i); } for (int i = 0; i < n; i++) ans += palin[i] / 2; for (int i = 0; i < n; i++) { for (char x = 'a'; x <= 'z'; x++) { c_ind = i, c_val = x - t[i]; for (int ind : p_cent[i]) { l = palin[ind], r = n+1; while (r - l > 1) { mid = (l + r) / 2; if (ind + mid - 1 < n && ind - mid + 1 >= 0 && check_palin(ind, mid, 1)) { l = mid; } else { r = mid; } } val[i][x - 'a'] += l / 2 - palin[ind] / 2; // cout << ind << " " << l << " " << palin[ind] << " " << x << "\n"; } m_val = max(m_val, val[i][x - 'a']); } } cout << ans + m_val << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif ll t; t = 1; // cin >> t; while(t--) { solve(); } return 0; }

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     freopen("input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:85:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  freopen("output.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...