oj.uz

답안 #47176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47176 2018-04-28T13:33:40 Z tmwilliamlin168 회문 (APIO14_palindrome) C++14
100 / 100
 747 ms 30144 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

inline void out(ll x) {
	ll rev=x;
	int cnt=0;
	while(rev%10==0) {
		rev/=10;
		++cnt;
	}
	rev=0;
	while(x) {
		rev=rev*10+x%10;
		x/=10;
	}
	while(rev) {
		putchar_unlocked(rev%10+'0');
		rev/=10;
	}
	while(cnt--)
		putchar_unlocked('0');
}

const int mxN=3e5, mxlgN=18;
int n, m=123, sa1[mxN], sa2[mxN], cl1[mxN*2], cl2[mxN], cnt[mxN+1], lcp[mxlgN+1][mxN], p[mxN*2+3];
char s[mxN+1], s2[mxN*2+3];

inline int lcpq(int l, int r) {
	int k=31-__builtin_clz(r-l+1);
	return min(lcp[k][l], lcp[k][r-(1<<k)+1]);
}

int main() {
	while(1) {
		char c=getchar_unlocked();
		if(c==' '||c=='\n'||c=='\r')
			break;
		s[n++]=c;
	}
	for(int i=0; i<n; ++i)
		cl1[i]=s[i];
	for(int l=1; l<=n; l*=2) {
		memset(cnt, 0, 4*m);
		for(int i=0; i<n; ++i)
			++cnt[cl1[i+l]];
		for(int i=1; i<m; ++i)
			cnt[i]+=cnt[i-1];
		for(int i=n-1; i>=0; --i)
			sa2[--cnt[cl1[i+l]]]=i;
		memset(cnt, 0, 4*m);
		for(int i=0; i<n; ++i)
			++cnt[cl1[i]];
		for(int i=1; i<m; ++i)
			cnt[i]+=cnt[i-1];
		for(int i=n-1; i>=0; --i)
			sa1[--cnt[cl1[sa2[i]]]]=sa2[i];
		m=0;
		for(int i=0; i<n; ++i) {
			if(!i||cl1[sa1[i]]!=cl1[sa1[i-1]]||cl1[sa1[i]+l]!=cl1[sa1[i-1]+l])
				++m;
			cl2[sa1[i]]=m;
		}
		++m;
		memcpy(cl1, cl2, 4*n);
	}
	s[n]='$';
	for(int i=0, k=0; i<n; ++i, k-=k>0) {
		if(cl1[i]>=n)
			continue;
		for(int j=sa1[cl1[i]]; s[i+k]==s[j+k]; ++k);
		lcp[0][cl1[i]]=k;
	}
//	for(int i=1; i<n; ++i)
//		cout << lcp[0][i] << " ";
//	cout << endl;
	for(int k=1; k<=mxlgN; ++k)
		for(int i=0; i<=n-(1<<k); ++i)
			lcp[k][i]=min(lcp[k-1][i], lcp[k-1][i+(1<<(k-1))]);
	int c=-1, r=-1;
	s2[0]='!', s2[1]='#', s2[2*n+2]='@';
	for(int i=0; i<n; ++i) {
		s2[2*i+2]=s[i];
		s2[2*i+3]='#';
	}
	ll ans=0;
	for(int i=1; i<=2*n+1; ++i) {
		if(r>=i)
			p[i]=min(r-i, p[2*c-i]);
//		cout << i << " " << p[i] << endl;
		while(s2[i+p[i]]==s2[i-p[i]]) {
			if((i-p[i])%2==0) {
				int j=(i-p[i])/2-1, l=p[i]+1, tl=1, lb, rb;
				assert(j<n);
//				cout << j << " " << l << endl;
				lb=1, rb=cl1[j]-1;
				assert(cl1[j]<=n);
				while(lb<=rb) {
					int mb=(lb+rb)/2;
					if(lcpq(mb, cl1[j]-1)>=l)
						rb=mb-1;
					else
						lb=mb+1;
				}
				tl+=cl1[j]-lb;
				lb=cl1[j], rb=n-1;
				while(lb<=rb) {
					int mb=(lb+rb)/2;
					if(lcpq(cl1[j], mb)>=l)
						lb=mb+1;
					else
						rb=mb-1;
				}
				tl+=rb-cl1[j]+1;
				ans=max((long long)tl*l, ans);
			}
			++p[i];
		}
		--p[i];
		if(i+p[i]>r) {
			c=i;
			r=i+p[i];
		}
//		cout << i << " " << p[i] << endl;
	}
	out(ans);
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 2 ms 688 KB Output is correct
10 Correct 2 ms 688 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 688 KB Output is correct
14 Correct 2 ms 688 KB Output is correct
15 Correct 2 ms 688 KB Output is correct
16 Correct 2 ms 688 KB Output is correct
17 Correct 2 ms 688 KB Output is correct
18 Correct 2 ms 688 KB Output is correct
19 Correct 2 ms 688 KB Output is correct
20 Correct 2 ms 688 KB Output is correct
21 Correct 2 ms 688 KB Output is correct
22 Correct 2 ms 688 KB Output is correct
23 Correct 2 ms 688 KB Output is correct
24 Correct 2 ms 688 KB Output is correct
25 Correct 2 ms 688 KB Output is correct
26 Correct 2 ms 688 KB Output is correct
27 Correct 2 ms 688 KB Output is correct
28 Correct 2 ms 712 KB Output is correct
29 Correct 2 ms 712 KB Output is correct
30 Correct 2 ms 712 KB Output is correct
31 Correct 2 ms 712 KB Output is correct
32 Correct 2 ms 712 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1532 KB Output is correct
2 Correct 6 ms 1532 KB Output is correct
3 Correct 6 ms 1532 KB Output is correct
4 Correct 8 ms 1532 KB Output is correct
5 Correct 8 ms 1532 KB Output is correct
6 Correct 7 ms 1532 KB Output is correct
7 Correct 6 ms 1532 KB Output is correct
8 Correct 9 ms 1536 KB Output is correct
9 Correct 9 ms 1536 KB Output is correct
10 Correct 7 ms 1536 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 9724 KB Output is correct
2 Correct 52 ms 9880 KB Output is correct
3 Correct 56 ms 9880 KB Output is correct
4 Correct 61 ms 9880 KB Output is correct
5 Correct 94 ms 9880 KB Output is correct
6 Correct 82 ms 9880 KB Output is correct
7 Correct 71 ms 9880 KB Output is correct
8 Correct 159 ms 9880 KB Output is correct
9 Correct 127 ms 9880 KB Output is correct
10 Correct 103 ms 9880 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 29872 KB Output is correct
2 Correct 177 ms 30036 KB Output is correct
3 Correct 164 ms 30036 KB Output is correct
4 Correct 178 ms 30036 KB Output is correct
5 Correct 630 ms 30144 KB Output is correct
6 Correct 271 ms 30144 KB Output is correct
7 Correct 283 ms 30144 KB Output is correct
8 Correct 747 ms 30144 KB Output is correct
9 Correct 711 ms 30144 KB Output is correct
10 Correct 622 ms 30144 KB Output is correct
11 Correct 168 ms 30144 KB Output is correct
12 Correct 649 ms 30144 KB Output is correct