Submission #46263

#	Time	Username	Problem	Language	Result	Execution time	Memory
46263		ikura355	Palindromes (APIO14_palindrome)	C++14	0 / 100	376 ms	71928 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5 + 5;
const int mlog = 19;
const ll mod = 1e9 + 7;
int n;
char s[maxn];
ll pw[maxn], en1[maxn], en2[maxn];
int can1[maxn], can2[maxn];
int lay, ra[maxn][21], sa[maxn];
ll add(ll x, ll y) {
	return ((x+y)%mod + mod)%mod;
}
ll mul(ll x, ll y) {
	return ((x*y)%mod + mod)%mod;
}
ll enc1(int l, int r) {
	return add(en1[r], -mul(en1[l], pw[r-l]));
}
ll enc2(int l, int r) {
	return add(en2[l], -mul(en2[r], pw[r-l]));
}
bool cmp(int x, int y) {
	if(ra[x][lay]!=ra[y][lay]) return ra[x][lay] < ra[y][lay];
	return (x+(1<<lay)<=n ? ra[x+(1<<lay)][lay] : -1) <= (y+(1<<lay)<=n ? ra[y+(1<<lay)][lay] : -1);
}
int lcp(int x, int y) {
    if(x==y) return n-x+1;
    int ret = 0;
    for(int i=mlog;i>=0;i--) {
        if(ra[x][i]==ra[y][i]) {
            ret += (1<<i);
            x += (1<<i); y += (1<<i);
        }
    }
    return ret;
}
int get(int i, int val) {
    int x = sa[i];
    int l, r, mid, posl = i, posr = i;
    l = 1; r = i;
    while(l<=r) {
        mid = (l+r)/2;
        if(lcp(sa[mid],x)>=val) {
            posl = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    l = i; r = n;
    while(l<=r) {
        mid = (l+r)/2;
        if(lcp(sa[mid],x)>=val) {
            posr = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    return posr-posl+1;
}
int main() {
	scanf(" %s",s+1);
	n = strlen(s+1);
	//1. longest palindrome
	pw[0] = 1;
	for(int i=1;i<=n;i++) pw[i] = mul(pw[i-1], 101);
	en1[0] = 0;
	for(int i=1;i<=n;i++) en1[i] = add(mul(en1[i-1], 101), s[i]);
	en2[n+1] = 0;
	for(int i=n;i>=1;i--) en2[i] = add(mul(en2[i+1], 101), s[i]);
	for(int i=1;i<=n;i++) {
        int l,r,mid,len;
        l = 0; r = min(i,n-i+1) - 1; len = 0;
		while(l<=r) {
			mid = (l+r)/2;
			if(enc1(i-mid,i+mid)==enc2(i-mid,i+mid)) {
				len = mid;
				l = mid+1;
			}
			else r = mid-1;
		}
        can1[i-len] = max(can1[i-len], len*2 + 1);
        l = 0; r = min(i,n-i) - 1; len = -1;
		while(l<=r) {
			mid = (l+r)/2;
			if(enc1(i-mid,1+i+mid)==enc2(i-mid,1+i+mid)) {
				len = mid;
				l = mid+1;
			}
			else r = mid-1;
		}
        can2[i-len] = max(can2[i-len], len*2 + 2);
	}
	for(int i=1;i<=n;i++) {
        can1[i] = max(can1[i], can1[i-1] - 2);
        can2[i] = max(can2[i], can2[i-1] - 2);
	}
	//2. longest match
	for(int i=1;i<=n;i++) ra[i][0] = s[i], sa[i] = i;
	for(lay=0;lay<=mlog;lay++) {
		sort(&sa[1],&sa[n+1],cmp);
		for(int i=1,cnt=0;i<=n;i++) {
			if(i==1 || !cmp(sa[i],sa[i-1])) cnt++;
			ra[sa[i]][lay+1] = cnt;
		}
	}
	long long ans = 0;
    for(int i=1;i<=n;i++) {
        int x = sa[i];
        ans = max(ans, (long long)get(i,can1[x])*can1[x]);
        ans = max(ans, (long long)get(i,can2[x])*can2[x]);
//        printf("%d : %d * %d\n",x,get(i,can1[x]),can1[x]);
//        printf("%d : %d * %d\n",x,get(i,can2[x]),can2[x]);
    }
    printf("%lld",ans);
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s",s+1);
  ~~~~~^~~~~~~~~~~

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