oj.uz

Submission #309489

# Submission time Handle Problem Language Result Execution time Memory
309489 2020-10-03T16:36:10 Z Kenzo_1114 Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 10 ms 8192 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const long long int MOD = 1e9 + 19;

int t;
long long int p[MAXN], sp[MAXN];
string s;	

void init()
{	
	p[0] = 1;
	for(int i = 1; i < MAXN; i++)
		p[i] = (p[i - 1] * 23) % MOD;
}

long long int Hash(int i, int j)
{
	long long int h = sp[j];
	if(i)	h = (h - sp[i - 1] + MOD) * p[i];
	return h % MOD;
}

void solve()
{
	cin >> s;

	int sz = (int) s.size();
	for(int i = 0; i < sz; i++)
	{	
		sp[i] = (p[sz - i - 1] * (s[i] - 'a')) % MOD;
		if(i)	sp[i] = (sp[i - 1] + sp[i]) % MOD;
	}

	int l = 0, r = sz - 1, ans = 0;
	while(l <= r)
	{
		if(l == r)	ans--;

		if(s[l] == s[r])	l++, r--;
		else
			for(int k = 1; l + k < sz; k++)
				if(Hash(l, l + k) == Hash(r - k, r))
				{	
					l += k + 1, r -= k + 1; 
					if(r < l)	ans--;
					break;	
				}

		ans += 2;
	}

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

int main ()
{
	init();

	scanf("%d", &t);
	while(t--)	solve();	
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -