Submission #864337

#TimeUsernameProblemLanguageResultExecution timeMemory
864337VN_AnhTuanPalinilap (COI16_palinilap)C++14
54 / 100
23 ms8796 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int, int> #define mp make_pair #define pb push_back #define bit(X,i) ((X>>i)&1) #define fori(i,d,c) for(int i = d; i <= c; ++ i) #define ford(i,d,c) for(int i = d; i >= c; -- i) #define all(V) V.begin(), V.end() #define RRH(V) V.resize(unique(all(V))-V.begin()) #define Task "palival" using namespace std; using ll = long long; using ld = long double; const int maxn = 1e5 + 5; const int maxm = 1e6 + 5; const int base = 101; string s, BASE_STRING; int n; void read() { cin >> s; BASE_STRING = s; n = s.size(); s = " " + s; } namespace sub1{ int f[105][105]; int calc() { ford(i,n,1) { fori(j,i,n) { if (j == i) f[i][j] = 1; else { if (s[i] == s[j]) { if (i + 1 == j) f[i][j] = 1; else f[i][j] = f[i+1][j-1]; } else f[i][j] = 0; } } } int res = 0; fori(i,1,n) fori(j,i,n) res += f[i][j]; return res; } void solve() { int res = calc(); fori(i,1,n) { char c = s[i]; fori(j,0,25) { if (s[i] - 'a' == j) continue; s[i] = char(j + 'a'); // if(calc() > res) { // cout << i << ' ' << s[i] << '\n'; // } res = max(res, calc()); } s[i] = c; } cout << res; } } ll Total_Result; namespace tester { int f[5005][5005]; int calc() { ford(i,n,1) { fori(j,i,n) { if (j == i) f[i][j] = 1; else { if (s[i] == s[j]) { if (i + 1 == j) f[i][j] = 1; else f[i][j] = f[i+1][j-1]; } else f[i][j] = 0; } } } int res = 0; fori(i,1,n) fori(j,i,n) res += f[i][j]; return res; } void solve() { int cs = -1, sum = 0; fori(i,2,n-1) { if (s[i-1] == s[i+1]) { int j = i-1; while(j - 1 >= 1 && s[j-1] == s[j]) j --; int j1 = i+1; while(j1 + 1 <= n && s[j1 + 1] == s[j1]) j1 ++; if (j1 - j + 1 > sum) { cs = i; sum = j1 - j + 1; } } } int res = calc(); if (1){ int sum1 = 0; int cs1 = 0, cs2 = n + 1; for(int i = 1; i <= n;) { int j1 = i; while(j1 + 1 <= n && s[j1 + 1] == s[i]) j1 ++; if (sum1 < j1 - i + 1) { sum1 = j1 - i + 1; cs1 = i - 1; cs2 = j1 + 1; } i = j1 + 1; } if (cs1 >= 1) { char c = s[cs1]; s[cs1] = s[cs1 + 1]; res = max(res, calc()); s[cs1] = c; } if (cs2 <= n) { char c = s[cs2]; s[cs2] = s[cs2-1]; res = max(res, calc()); s[cs2] = c; } Total_Result = max(Total_Result, 1ll * res); } if (cs != -1){ s[cs] = s[cs-1]; res = max(res, calc()); Total_Result = max(Total_Result, 1ll * res); } } } namespace sub2 { #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define REP(i, n) FOR(i, 0, n) #define TRACE(x) cerr << #x << " = " << x << endl #define _ << " " << typedef pair<int, int> point; const ll MOD = 1e9 + 7; const ll BAZA = 1307; string s; int h[maxn], h_[maxn], pot[maxn]; void calcHash(){ pot[0] = 1; h[0] = s[0]; FOR(i, 1, (int)s.size()){ h[i] = ((ll)h[i - 1] * BAZA + s[i]) % MOD; pot[i] = (ll)pot[i - 1] * BAZA % MOD; } h_[0] = s[s.size() - 1]; for(int i = s.size() - 2, cnt = 1; i >= 0; --i, ++cnt) h_[cnt] = ((ll)h_[cnt - 1] * BAZA + s[i]) % MOD; } ll calc(ll x, ll y){ ll k = 0; if(x) k = (ll)h[x - 1] * pot[y] % MOD; return ((((ll)h[x + y - 1] - k) % MOD) + MOD) % MOD; } ll calc_(ll x, ll y){ ll k = 0; if(x) k = (ll)h_[x - 1] * pot[y] % MOD; return ((((ll)h_[x + y - 1] - k) % MOD) + MOD) % MOD; } ll cntDec[maxn]; ll decrease[maxn]; ll increase[maxn], letInc[maxn][30]; void solve(){ ios_base::sync_with_stdio(false); cin.tie(0), s = BASE_STRING; calcHash(); ll sol = 0; int len = s.size(); REP(i, len){ //neparni ll lo = 1, hi = min(i + 1, len - i); while(lo < hi){ ll mid = (lo + hi + 1) >> 1; /*if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){ assert(s.size() == 0); }*/ if(calc(i, mid) == calc_(len - i - 1, mid)) lo = mid; else hi = mid - 1; } cntDec[i - lo + 1] ++; cntDec[i + 1] -= 2; cntDec[i + lo + 1] ++; sol += lo; increase[i] += lo; ll jump = lo + 1; lo = 0, hi = max(0LL, min(i + 1, len - i) - jump); while(lo < hi){ ll mid = (lo + hi + 1) >> 1; /*if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){ assert(s.size() == 0); }*/ if(calc(i + jump, mid) == calc_(len - i + jump - 1, mid)) lo = mid; else hi = mid - 1; } letInc[i + jump - 1][s[i - jump + 1] - 'a'] += lo + 1; letInc[i - jump + 1][s[i + jump - 1] - 'a'] += lo + 1; if(i == len - 1) continue; //neparni lo = 0, hi = max(0, min(i + 1, len - i - 1)); while(lo < hi){ ll mid = (lo + hi + 1) >> 1; /*if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){ assert(s.size() == 0); }*/ if(calc(i + 1, mid) == calc_(len - i - 1, mid)) lo = mid; else hi = mid - 1; } sol += lo; if(lo){ cntDec[i - lo + 1] ++; cntDec[i + 1] --; cntDec[i + 2] --; cntDec[i + lo + 2] ++; } jump = lo + 1; lo = 0, hi = max(0LL, min(i + 1, len - i - 1) - jump); while(lo < hi){ ll mid = (lo + hi + 1) >> 1; /*if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){ assert(s.size() == 0); }*/ if(calc(i + jump + 1, mid) == calc_(len - i + jump - 1, mid)) lo = mid; else hi = mid - 1; } letInc[i + jump][s[i - jump + 1] - 'a'] += lo + 1; letInc[i - jump + 1][s[i + jump] - 'a'] += lo + 1; } ll cnt = 0, curr = 0; REP(i, len){ cnt += cntDec[i]; curr += cnt; decrease[i] = curr; } ll best = 0; REP(i, len) REP(j, 26){ best = max(best, increase[i] + letInc[i][j] - decrease[i]); } cout << sol + best; } } void solve() { Total_Result = n; if (n <= 100) sub1::solve(); else if (n <= 5000) sub2::solve(); else { tester::solve(); cout << Total_Result; } } int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } read(); solve(); cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; }

Compilation message (stderr)

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