oj.uz

Submission #500288

# Submission time Handle Problem Language Result Execution time Memory
500288 2021-12-30T15:41:05 Z pooyashams Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 51 ms 15044 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 1e6+10;
const int base = 541;
const int mod = 1e9+7;

int kmp[maxn];
int bpw[maxn];
int n;
string str;

inline void solve()
{
	cin >> str;
	n = str.size();
	int o = 0;
	int s = 0;
	int e = n-1;
	int h1 = str[s++];
	int h2 = str[e--];
	int l = 1;
	int mid = n/2 - (1-n%2);
	for(int i = 0; i < mid; i++)
	{
		if(h1 == h2)
		{
			o += 2;
			h1 = str[s++];
			h2 = str[e--];
			l = 1;
		}
		else
		{
			h1 = (1ll*h1*base+str[s++]) % mod;
			h2 = (1ll*bpw[l++]*str[e--]+h2) % mod;
		}
	}
	if(h1 == h2 and n % 2 == 0)
		o += 2;
	else
		o += 1;
	cout << o << endl;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	bpw[0] = 1;
	for(int i = 1; i < maxn; i++)
		bpw[i] = 1ll*bpw[i-1]*base%mod;
	int T; cin >> T;
	while(T--)
	{
		solve();
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4228 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4212 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4228 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4212 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 7 ms 4172 KB Output is correct
7 Correct 8 ms 4152 KB Output is correct
8 Correct 7 ms 4176 KB Output is correct
9 Correct 7 ms 4172 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4228 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4212 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 7 ms 4172 KB Output is correct
7 Correct 8 ms 4152 KB Output is correct
8 Correct 7 ms 4176 KB Output is correct
9 Correct 7 ms 4172 KB Output is correct
10 Correct 8 ms 4296 KB Output is correct
11 Correct 9 ms 4300 KB Output is correct
12 Correct 9 ms 4244 KB Output is correct
13 Correct 10 ms 4248 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4228 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4212 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 7 ms 4172 KB Output is correct
7 Correct 8 ms 4152 KB Output is correct
8 Correct 7 ms 4176 KB Output is correct
9 Correct 7 ms 4172 KB Output is correct
10 Correct 8 ms 4296 KB Output is correct
11 Correct 9 ms 4300 KB Output is correct
12 Correct 9 ms 4244 KB Output is correct
13 Correct 10 ms 4248 KB Output is correct
14 Correct 41 ms 15044 KB Output is correct
15 Correct 31 ms 10388 KB Output is correct
16 Correct 51 ms 14508 KB Output is correct
17 Correct 22 ms 9976 KB Output is correct