답안 #47164 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47164	2018-04-28T13:16:34 Z	tmwilliamlin168	회문 (APIO14_palindrome)	C++14	73 / 100	694 ms	33004 KB

palindrome

#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+1];
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;
//				cout << j << " " << l << endl;
				lb=1, rb=cl1[j]-1;
				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	436 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	488 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	544 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	2 ms	600 KB	Output is correct
11	Correct	2 ms	608 KB	Output is correct
12	Correct	2 ms	612 KB	Output is correct
13	Correct	2 ms	616 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	2 ms	748 KB	Output is correct
16	Correct	2 ms	748 KB	Output is correct
17	Correct	2 ms	748 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Correct	2 ms	748 KB	Output is correct
20	Correct	2 ms	748 KB	Output is correct
21	Correct	2 ms	748 KB	Output is correct
22	Correct	2 ms	748 KB	Output is correct
23	Correct	2 ms	748 KB	Output is correct
24	Correct	2 ms	748 KB	Output is correct
25	Correct	2 ms	752 KB	Output is correct
26	Correct	2 ms	788 KB	Output is correct
27	Correct	2 ms	788 KB	Output is correct
28	Correct	2 ms	788 KB	Output is correct
29	Correct	2 ms	788 KB	Output is correct
30	Correct	2 ms	904 KB	Output is correct
31	Correct	2 ms	904 KB	Output is correct
32	Correct	2 ms	916 KB	Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1844 KB	Output is correct
2	Correct	6 ms	1856 KB	Output is correct
3	Correct	6 ms	1884 KB	Output is correct
4	Correct	6 ms	1912 KB	Output is correct
5	Correct	7 ms	1924 KB	Output is correct
6	Correct	7 ms	1952 KB	Output is correct
7	Correct	6 ms	1964 KB	Output is correct
8	Correct	11 ms	1964 KB	Output is correct
9	Correct	10 ms	1988 KB	Output is correct
10	Correct	7 ms	2032 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	10348 KB	Output is correct
2	Correct	54 ms	10576 KB	Output is correct
3	Correct	51 ms	10576 KB	Output is correct
4	Correct	61 ms	10776 KB	Output is correct
5	Correct	99 ms	10904 KB	Output is correct
6	Correct	83 ms	10976 KB	Output is correct
7	Correct	69 ms	11076 KB	Output is correct
8	Correct	153 ms	11176 KB	Output is correct
9	Correct	141 ms	11232 KB	Output is correct
10	Correct	89 ms	11384 KB	Output is correct

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	174 ms	31556 KB	Output is correct
2	Correct	185 ms	32124 KB	Output is correct
3	Correct	167 ms	32272 KB	Output is correct
4	Correct	177 ms	32676 KB	Output is correct
5	Correct	694 ms	33004 KB	Output is correct
6	Runtime error	123 ms	33004 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Halted	0 ms	0 KB	-

답안 #47164

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
0 / 27.0