oj.uz

Submission #320494

# Submission time Handle Problem Language Result Execution time Memory
320494 2020-11-08T21:19:12 Z MahdiBahramian Palindromic Partitions (CEOI17_palindromic) C++11
100 / 100
 233 ms 44188 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define var auto
#define F first
#define S second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Mod1 = 1e9 + 7;
const int Mod2 = 1e9 + 21;
const int BASE = 37;
const int Max = 1e6 + 10;

ll h1[Max];
ll pw1[Max];
ll h2[Max];
ll pw2[Max];

bool check(int l , int r , int x , int y)
{
	r++ , y++;
	ll f1 = (h1[r] - h1[l] * pw1[r - l] % Mod1 + Mod1) % Mod1;
	ll f2 = (h2[r] - h2[l] * pw2[r - l] % Mod2 + Mod2) % Mod2;
	ll g1 = (h1[y] - h1[x] * pw1[y - x] % Mod1 + Mod1) % Mod1;
	ll g2 = (h2[y] - h2[x] * pw2[y - x] % Mod2 + Mod2) % Mod2;
	return f1 == g1 && f2 == g2;
}

void solve()
{
	string s; cin >> s;
	int n = s.size();
	pw1[0] = pw2[0] = 1;
	for(int i = 1; i <= n ; i++)
	{
		h1[i] = (h1[i - 1] * BASE + s[i - 1]) % Mod1;
		h2[i] = (h2[i - 1] * BASE + s[i - 1]) % Mod2;
		pw1[i] = pw1[i - 1] * BASE % Mod1;
		pw2[i] = pw2[i - 1] * BASE % Mod2;
	}

	int cnt = 0;
	int L = 0 , R = n - 1;
	for(int l = L , r = R ; l < r ; l++ , r--)
	{
		if(check(L , l , r , R))
		{
			//cout << "*" << l - L + 1 << '\n';
			L = l + 1;
			R = r - 1;
			cnt += 2;
		}
	}
	if(L <= R)
		cnt++;
	cout << cnt << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;cin >> t;
	while(t--)
		solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 3 ms 744 KB Output is correct
13 Correct 3 ms 748 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 3 ms 744 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 233 ms 44188 KB Output is correct
15 Correct 130 ms 39296 KB Output is correct
16 Correct 223 ms 43296 KB Output is correct
17 Correct 128 ms 23452 KB Output is correct