oj.uz

Submission #243871

# Submission time Handle Problem Language Result Execution time Memory
243871 2020-07-02T03:44:59 Z luciocf Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 609 ms 19996 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;
const int mod = 1e9+7;
const int P = 31;

int suf[maxn];
int pot[maxn];

int main(void)
{
	int tc;
	cin >> tc;

	pot[0] = 1;
	for (int i = 1; i < maxn; i++)
		pot[i] = (1ll*P*pot[i-1])%mod;

	while (tc--)
	{
		string s;
		cin >> s;

		suf[s.size()] = 0;

		for (int i = s.size()-1; i >= 0; i--)
			suf[i] = (1ll*suf[i+1]*P + 1ll*(int)(s[i]-'a'+1))%mod;

		int l = 0, r = s.size()-1, len = 0;
		int hsh = 0, ans = 0;

		while (l <= r)
		{
			++len;
			hsh = (1ll*hsh + 1ll*pot[len-1]*(int)(s[l]-'a'+1))%mod;

			if (hsh == (suf[r] - (1ll*suf[r+len]*pot[len])%mod + mod)%mod)
			{
				if (l == r) ans++;
				else ans += 2;
				len = 0, hsh = 0;
			}


			l++, r--;
		}

		if (len) ans++;

		printf("%d\n", ans);
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4224 KB Output is correct
2 Correct 15 ms 4172 KB Output is correct
3 Correct 12 ms 4096 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 12 ms 4224 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4224 KB Output is correct
2 Correct 15 ms 4172 KB Output is correct
3 Correct 12 ms 4096 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 12 ms 4224 KB Output is correct
6 Correct 13 ms 4224 KB Output is correct
7 Correct 12 ms 4224 KB Output is correct
8 Correct 12 ms 4224 KB Output is correct
9 Correct 12 ms 4224 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4224 KB Output is correct
2 Correct 15 ms 4172 KB Output is correct
3 Correct 12 ms 4096 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 12 ms 4224 KB Output is correct
6 Correct 13 ms 4224 KB Output is correct
7 Correct 12 ms 4224 KB Output is correct
8 Correct 12 ms 4224 KB Output is correct
9 Correct 12 ms 4224 KB Output is correct
10 Correct 18 ms 4352 KB Output is correct
11 Correct 15 ms 4480 KB Output is correct
12 Correct 17 ms 4352 KB Output is correct
13 Correct 17 ms 4480 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4224 KB Output is correct
2 Correct 15 ms 4172 KB Output is correct
3 Correct 12 ms 4096 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 12 ms 4224 KB Output is correct
6 Correct 13 ms 4224 KB Output is correct
7 Correct 12 ms 4224 KB Output is correct
8 Correct 12 ms 4224 KB Output is correct
9 Correct 12 ms 4224 KB Output is correct
10 Correct 18 ms 4352 KB Output is correct
11 Correct 15 ms 4480 KB Output is correct
12 Correct 17 ms 4352 KB Output is correct
13 Correct 17 ms 4480 KB Output is correct
14 Correct 609 ms 19996 KB Output is correct
15 Correct 330 ms 15164 KB Output is correct
16 Correct 567 ms 19416 KB Output is correct
17 Correct 324 ms 12896 KB Output is correct