oj.uz

Submission #46254

# Submission time Handle Problem Language Result Execution time Memory
46254 2018-04-18T09:31:26 Z ikura355 Palindromes (APIO14_palindrome) C++14
0 / 100
 355 ms 81984 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 + 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][25], 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 ra[x+(1<<lay)][lay] <= ra[y+(1<<lay)][lay];
}
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 700 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Runtime error 39 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 1296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 3780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 27896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 355 ms 81984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -