답안 #320619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320619	2020-11-09T09:19:48 Z	woldis4	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	3402 ms	18204 KB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int XN = 1e6+7, md = 1e9+7, base = 257;

ll t, n, p[XN], pw[XN];
string s;

ll tavan(ll a, ll b){
	if (b == 0)	return 1;
	ll adad = tavan(a, b/2);
	return (adad*adad % md) * max(1LL, (b%2)*a) % md;
}

ll substr(int L, int R){
	if (L == 0)	return p[R];
	return ((p[R]-p[L-1]+md) % md) * tavan(pw[L], md-2) % md;
}

void pre(){
	p[0] = int(s[0]);
	for (int i = 1; i < n; ++i)	p[i] = p[i-1] + pw[i]*ll(s[i]), p[i] %= md;
}

int main(){
	cin >> t;
	pw[0] = 1;
	for (int i = 1; i < XN; ++i)	pw[i] = (pw[i-1]*base)%md;
	while (t--){
		cin >> s;
		n = s.size();
		pre();
		ll L = 0, R = n-1, cnt1 = 0, cnt2 = n-1, ans = 0;
		ll flg = 1;
		while (R > L){
			if (substr(cnt1, L) == substr(R, cnt2)){
				if (n%2 == 0 && L == n/2-1 && R == n/2)	flg = 0;
				cnt1 = L+1, cnt2 = R-1, ans += 2;
			}
			++L, R--;
		}
		cout << ans+flg << '\n';
	}
	return 0;
}

Subtask #1

15.0 / 15.0

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

Subtask #2

20.0 / 20.0

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

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	8172 KB	Output is correct
2	Correct	9 ms	8172 KB	Output is correct
3	Correct	9 ms	8172 KB	Output is correct
4	Correct	10 ms	8172 KB	Output is correct
5	Correct	9 ms	8172 KB	Output is correct
6	Correct	10 ms	8172 KB	Output is correct
7	Correct	10 ms	8172 KB	Output is correct
8	Correct	10 ms	8172 KB	Output is correct
9	Correct	12 ms	8172 KB	Output is correct
10	Correct	41 ms	8300 KB	Output is correct
11	Correct	26 ms	8300 KB	Output is correct
12	Correct	45 ms	8300 KB	Output is correct
13	Correct	39 ms	8300 KB	Output is correct

Subtask #4

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	8172 KB	Output is correct
2	Correct	9 ms	8172 KB	Output is correct
3	Correct	9 ms	8172 KB	Output is correct
4	Correct	10 ms	8172 KB	Output is correct
5	Correct	9 ms	8172 KB	Output is correct
6	Correct	10 ms	8172 KB	Output is correct
7	Correct	10 ms	8172 KB	Output is correct
8	Correct	10 ms	8172 KB	Output is correct
9	Correct	12 ms	8172 KB	Output is correct
10	Correct	41 ms	8300 KB	Output is correct
11	Correct	26 ms	8300 KB	Output is correct
12	Correct	45 ms	8300 KB	Output is correct
13	Correct	39 ms	8300 KB	Output is correct
14	Correct	3136 ms	17752 KB	Output is correct
15	Correct	1354 ms	18204 KB	Output is correct
16	Correct	3402 ms	18088 KB	Output is correct
17	Correct	1908 ms	13592 KB	Output is correct