Submission #863868

#	Time	Username	Problem	Language	Result	Execution time	Memory
863868		tradz	Palinilap (COI16_palinilap)	C++14	0 / 100	1054 ms	2652 KiB

palinilap

// Author : Hoang Van Tra - HSGS Bac Giang
// Train VOI 2023 - 2024

#include <bits/stdc++.h>

using namespace std;

// -------------------------------------------------------INDEF-----------------------------------------------------------------------

#define For(i,a,b) for(int i = a; i <= b; i++)
#define Ford(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define RRH(v) v.resize(unique(all(v)) - v.begin())
const int  N = 1e6+7;
const int M = 1e9+7;
const ll oo = 1e18;
const int block = 708;
namespace IO
{
    #define getchar() (ipos==iend and (iend=(ipos=_ibuf)+fread(_ibuf,1,__bufsize,stdin),ipos==iend)?EOF:*ipos++)
    #define putchar(ch) (opos==oend?fwrite(_obuf,1,__bufsize,stdout),opos=_obuf:0,*opos++=(ch))
    #define __bufsize (1<<20)
    char _ibuf[__bufsize],_obuf[__bufsize],_stk[20];
    char *ipos=_ibuf,*iend=_ibuf,*opos=_obuf,*oend = _obuf+__bufsize,*stkpos = _stk;
    struct END{~END(){fwrite(_obuf,1,opos-_obuf,stdout);}}__;
    inline void read(int&x)
    {
        register int f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void readll(ll&x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void write(ll x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
};

using namespace IO;

string s;

namespace sub2 {
	const ll base1 = 31;
	const ll base2 = 33;
	const ll mod1 = 1e9 + 7;
	const ll mod2 = 2000037241ll;

	int n;

	ll p[5009], h[5009], ha[5009];
	int cnt[N];
	ll ans = 0;

	ll pre(int l, int r) {
		return (h[r] - h[l - 1] * p[r - l + 1] + 1ll * mod1 * mod1) % mod1;
	}

	ll suf(int l, int r) {
		return (ha[r] - ha[l - 1] * p[r - l + 1] + 1ll * mod1 * mod1) % mod1;
	}

	bool check(int l, int r) {
		if(pre(l, r) == suf(n - r + 1, n - l + 1)) return 1;
		return 0;
	}

	ll po[5009], hasa[5009], has[5009];

	ll get_pre(int l, int r) {
		return (hasa[r] - hasa[l - 1] * po[r - l + 1] + 1ll * mod2 * mod2) % mod2;
	}

	ll get_suf(int l, int r) {
		return (has[r] - has[l - 1] * po[r - l + 1] + 1ll * mod2 * mod2) % mod2;
	}

	bool check2(int l, int r) {
		if(get_pre(l, r) == get_suf(n - r + 1, n - l + 1)) return 1;
		return 0;
	}

	void solve() {
		n = s.size();
		s = ' ' + s;
		po[0] = p[0] = 1;
		h[0] = hasa[0] = ha[0] = has[0] = 0;

		// h , ha la mod1
		// hasa, has la mod2

		For(i,1,n) {
			p[i] = p[i - 1] * base1 * 1ll;
			po[i] = po[i - 1] * base2 * 1ll;
			p[i] %= mod1;
			po[i] %= mod2;

			h[i] = (h[i - 1] * base1 + s[i] - 'a' + 1) % mod1;
			hasa[i] = (hasa[i - 1] * base2 + s[i] - 'a' + 1) % mod2;
			ha[i] = (ha[i - 1] * base1 * 1ll + s[n - i + 1] - 'a' + 1) % mod1;
			has[i] = (has[i - 1] * base2 * 1ll + s[n - i + 1] - 'a' + 1) % mod2;
		}

		For(i,1,n) {
			For(j,i,n) {
				if(i == j) {
					ans++;
					cnt[i]++;
				}
				else {
					if(check(i, j) && check2(i, j)) {
						cnt[i]++;
						cnt[j]++;
						ans++;
					}
				}
			}
		}

		For(i,1,n) {
			for(char c = 'a'; c <= 'z'; c++) {
				ll tmp = ans - cnt[i];
				For(j,1,n) {
					if(i == j) tmp++;
					else {
						if(i > j) {
							int l = j;
							int r = i;
							ll hashing = ((c - 'a' + 1) * 1ll * p[r - l] % mod1 + pre(l, r - 1)) % mod1;
							ll hashingg = (suf(l + 1, r) * base1 + (c - 'a' + 1) * 1ll % mod1) % mod1;
							if(hashingg != hashing) continue;
							else {
								hashing = ((c - 'a' + 1) * 1ll * po[r - l] % mod2 + get_pre(l, r - 1)) % mod2;
								hashingg = (get_suf(l + 1, r) * base2 + (c - 'a' + 1) * 1ll % mod2) % mod2;
								if(hashingg == hashing) tmp++;
							}
						}

						else {

							int l = i;
							int r = j;
							
							ll hashing = ((c - 'a' + 1) * 1ll + pre(l + 1, r) * base1 % mod1) % mod1;
							ll hashingg = ((c - 'a' + 1) * 1ll * p[r - l] % mod1 + suf(l, r - 1) * base1 % mod1) % mod1;
							if(hashingg != hashing) continue;
							else {
								hashing = ((c - 'a' + 1) * 1ll + get_pre(l + 1, r) * base2 % mod2) % mod2;
								hashingg = ((c - 'a' + 1) * 1ll * po[r - l] % mod2 + get_suf(l, r - 1) * base2 % mod2) % mod2;
								if(hashingg == hashing) tmp++;
							}
						}
					}
				}
				ans = max(ans, tmp);
			}
		}

		cout << ans;
	}
}
// -------------------------------------------------------ENDEF----------------------------------------------------------------------

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);

    #define TASK ""
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    cin >> s;
    int n = s.size();
    if(n <= 5000) {
    	sub2 :: solve();
    }    

    // else {
    // 	subac :: solve();
    // }

    return 0;
}

Compilation message (stderr)

palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46