oj.uz

Submission #868698

# Submission time Handle Problem Language Result Execution time Memory
868698 2023-11-01T15:33:20 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 110 ms 28568 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int maxn=1e6+7;
const int base=9973;
const int mod=1e9+7;
int pw[maxn], hsh[maxn];

int get(int l, int r)
{
	return (hsh[r]-hsh[l-1]*pw[r-l+1]+mod*mod)%mod;
}

void solve()
{
	string s; cin >> s;
	int N=s.size();
	s=' '+s;
	for (int i=1; i<=N; i++) hsh[i]=(hsh[i-1]*base+s[i]-'a'+1)%mod;
	int l=1, r=N, ans=0;
	while (l<=r)
	{
		if (l==r)
		{
			ans++;
			break;
		}
		for (int i=l; i<=N/2; i++)
		{
			if (get(l, i)==get(N-i+1, r))
			{
				ans+=2;
				l=i+1;
				r=N-i;
				goto GT;
			}
		}
		ans+=(l<r);
		break;
		GT:;
		if (l==r)
		{
			ans++;
			break;
		}
	}
	cout<<ans<<endl;
}

signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	pw[0]=1;
	for (int i=1; i<=maxn; i++) pw[i]=pw[i-1]*base%mod;
	int t; cin >> t;
	while(t--) solve();
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:55:35: warning: iteration 1000006 invokes undefined behavior [-Waggressive-loop-optimizations]
   55 |  for (int i=1; i<=maxn; i++) pw[i]=pw[i-1]*base%mod;
      |                              ~~~~~^~~~~~~~~~~~~~~~~
palindromic.cpp:55:17: note: within this loop
   55 |  for (int i=1; i<=maxn; i++) pw[i]=pw[i-1]*base%mod;
      |                ~^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9572 KB Output is correct
2 Correct 8 ms 9560 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 6 ms 9784 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9572 KB Output is correct
2 Correct 8 ms 9560 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 6 ms 9784 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct
6 Correct 6 ms 9564 KB Output is correct
7 Correct 6 ms 9564 KB Output is correct
8 Correct 6 ms 9680 KB Output is correct
9 Correct 6 ms 9796 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9572 KB Output is correct
2 Correct 8 ms 9560 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 6 ms 9784 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct
6 Correct 6 ms 9564 KB Output is correct
7 Correct 6 ms 9564 KB Output is correct
8 Correct 6 ms 9680 KB Output is correct
9 Correct 6 ms 9796 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 6 ms 9820 KB Output is correct
12 Correct 8 ms 9992 KB Output is correct
13 Correct 7 ms 9820 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9572 KB Output is correct
2 Correct 8 ms 9560 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 6 ms 9784 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct
6 Correct 6 ms 9564 KB Output is correct
7 Correct 6 ms 9564 KB Output is correct
8 Correct 6 ms 9680 KB Output is correct
9 Correct 6 ms 9796 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 6 ms 9820 KB Output is correct
12 Correct 8 ms 9992 KB Output is correct
13 Correct 7 ms 9820 KB Output is correct
14 Correct 110 ms 28568 KB Output is correct
15 Correct 60 ms 23496 KB Output is correct
16 Correct 100 ms 27600 KB Output is correct
17 Correct 62 ms 20548 KB Output is correct