oj.uz

답안 #47170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47170 2018-04-28T13:25:14 Z tmwilliamlin168 회문 (APIO14_palindrome) C++14
73 / 100
 628 ms 30000 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], 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 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 636 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 636 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 2 ms 636 KB Output is correct
18 Correct 2 ms 636 KB Output is correct
19 Correct 2 ms 636 KB Output is correct
20 Correct 2 ms 636 KB Output is correct
21 Correct 2 ms 636 KB Output is correct
22 Correct 2 ms 636 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 688 KB Output is correct
29 Correct 2 ms 688 KB Output is correct
30 Correct 2 ms 688 KB Output is correct
31 Correct 2 ms 688 KB Output is correct
32 Correct 2 ms 688 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 740 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 2 ms 740 KB Output is correct
4 Correct 2 ms 740 KB Output is correct
5 Correct 2 ms 740 KB Output is correct
6 Correct 3 ms 740 KB Output is correct
7 Correct 2 ms 820 KB Output is correct
8 Correct 2 ms 820 KB Output is correct
9 Correct 2 ms 820 KB Output is correct
10 Correct 2 ms 820 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 2 ms 876 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 6 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Correct 9 ms 1536 KB Output is correct
9 Correct 9 ms 1536 KB Output is correct
10 Correct 8 ms 1536 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 9724 KB Output is correct
2 Correct 69 ms 9852 KB Output is correct
3 Correct 53 ms 9852 KB Output is correct
4 Correct 61 ms 9884 KB Output is correct
5 Correct 100 ms 9908 KB Output is correct
6 Correct 90 ms 9908 KB Output is correct
7 Correct 69 ms 9908 KB Output is correct
8 Correct 160 ms 9908 KB Output is correct
9 Correct 130 ms 9908 KB Output is correct
10 Correct 96 ms 9912 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 29832 KB Output is correct
2 Correct 173 ms 30000 KB Output is correct
3 Correct 169 ms 30000 KB Output is correct
4 Correct 178 ms 30000 KB Output is correct
5 Correct 628 ms 30000 KB Output is correct
6 Runtime error 122 ms 30000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -