Submission #588382

#	Time	Username	Problem	Language	Result	Execution time	Memory
588382		MrDeboo	Palindromes (APIO14_palindrome)	C++17	0 / 100	71 ms	36656 KiB

palindrome

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;
#define MAXLEN 1000010
constexpr uint64_t Hmod= (1ULL << 61) - 1;
const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (Hmod / 3) + (Hmod / 3);
uint64_t base_pow[MAXLEN];
int64_t modmul(uint64_t a, uint64_t b){
    uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
    uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
    uint64_t ret = (l & Hmod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & Hmod) + (ret >> 61);
    ret = (ret & Hmod) + (ret >> 61);
    return ret - 1;
}
void init(){
    base_pow[0] = 1;
    for (int i = 1; i < MAXLEN; i++){
        base_pow[i] = modmul(base_pow[i - 1], base);
    }
}
struct PolyHash{
    vector<int64_t> pref, suff;
    PolyHash() {}
    template <typename T>
    PolyHash(const vector<T>& ar){
        if (!base_pow[0]) init();
        int n = ar.size();
        assert(n < MAXLEN);
        pref.resize(n + 3, 0), suff.resize(n + 3, 0);
        for (int i = 1; i <= n; i++){
            pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
            if (pref[i] >= Hmod) pref[i] -= Hmod;
        }

        for (int i = n; i >= 1; i--){
            suff[i] = modmul(suff[i + 1], base) + ar[i - 1] + 997;
            if (suff[i] >= Hmod) suff[i] -= Hmod;
        }
    }
    PolyHash(const char* str)
        : PolyHash(vector<char> (str, str + strlen(str))) {}

    uint64_t get_hash(int l, int r){
        int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
        return h < 0 ? h + Hmod : h;
    }
    uint64_t rev_hash(int l, int r){
        int64_t h = suff[l + 1] - modmul(base_pow[r - l + 1], suff[r + 2]);
        return h < 0 ? h + Hmod : h;
    }
};
PolyHash PolyH(string s){
	vector<char>v;
	for(auto &i:s)v.push_back(i);
	return PolyHash(v);
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string s;
	cin>>s;
	PolyHash h=PolyH(s);
	int ans=0,cnt=0,n=s.size();
	map<int,vector<pair<int,int>>>mp;
	map<int,pair<int,int>>mop;
	for(int i=0;i<n;i++){
		cnt++;
		if(i==n-1||s[i]!=s[i+1]){
			for(int w=0;w<cnt;w++){
				mop[h.get_hash(i-w,i)].first=w+1;
				mop[h.get_hash(i-w,i)].second+=cnt-w;
			}
            if(mp[s[i]].size()){
                int k=min(cnt,mp[s[i]].back().second);
                if(h.get_hash(mp[s[i]].back().first-k,i-cnt+k)==h.rev_hash(mp[s[i]].back().first-k,i-cnt+k)){
                    mop[h.get_hash(mp[s[i]].back().first-k,i-cnt+k)].first=i-cnt-mp[s[i]].back().first+1+k*2;
                    mop[h.get_hash(mp[s[i]].back().first-k,i-cnt+k)].second++;
                }
            }
			mp[s[i]].push_back({i+1,cnt});
			cnt=0;
		}
	}
	for(auto &i:mop)ans=max(ans,i.second.second*i.second.first);
	for(int i=0;i<n;i++){
		int l=i,r=n-i-1,mid,f=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(h.get_hash(i,i+mid)==h.rev_hash(i-mid,i)){f=mid;l=mid+1;}
			else r=mid-1;
		}
		if(f==-1)continue;
		ans=max(ans,f*2+1);
	}
	for(int i=1;i<n;i++){
		int l=i-1,r=n-i-1,mid,f=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(h.get_hash(i,i+mid)==h.rev_hash(i-1-mid,i-1)){f=mid;l=mid+1;}
			else r=mid-1;
		}
		if(f==-1)continue;
		ans=max(ans,f*2+2);
	}
	cout<<ans;
}

Compilation message (stderr)

palindrome.cpp: In instantiation of 'PolyHash::PolyHash(const std::vector<_Tp>&) [with T = char]':
palindrome.cpp:48:57:   required from here
palindrome.cpp:39:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   39 |             if (pref[i] >= Hmod) pref[i] -= Hmod;
palindrome.cpp:44:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   44 |             if (suff[i] >= Hmod) suff[i] -= Hmod;

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27