oj.uz

Submission #934230

# Submission time Handle Problem Language Result Execution time Memory
934230 2024-02-27T02:51:53 Z Faisal_Saqib Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 296 ms 27064 KB 
#include <iostream>
using namespace std;
#define int long long
#define ll long long
const ll base=717;
const ll mod=1e9+9;
const int N=1e6+100;
ll n,pre[N],pw[N];

void Hash(string& s)
{
    n=(int)s.size();
    pre[0]=0;
    for(int i=1;i<=n;i++)
    {
    	pre[i]=(pre[i-1]*base)%mod;
    	pre[i]+=(s[i-1]-'a');
    	pre[i]%=mod;
    }
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=(pw[i-1]*base)%mod;
}
// (l,r)
// s[r]
// s[l]*(r-l) + .. s[r]
// s[l-1]
// s[l-1]
int get(int l,int r)//inclusive 1-based indexing
{
	return (pre[r]+mod-((pre[l-1]*pw[r-l+1])%mod))%mod;
}
void solve()
{
	string s;
	cin>>s;
	Hash(s);
	int l=0;
	int r=n+1;
	int cnt=0;
	while((l+1)<r)
	{
		int sl=l;
		int sr=r;
		for(int len=1;len<=(r-l-1);len++)	
		{
			if(get(l+1,l+len)==get(r-len,r-1))
			{
				cnt++;
				cnt+=((l+1!=(r-len)) or ((l+len)!=(r-1)));
				l+=len;
				r-=len;
				break;
			}
		}
	}
	cout<<cnt<<endl;
	// both endpoints are exclusive	(l,r)
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

Compilation message

palindromic.cpp: In function 'void solve()':
palindromic.cpp:43:7: warning: unused variable 'sl' [-Wunused-variable]
   43 |   int sl=l;
      |       ^~
palindromic.cpp:44:7: warning: unused variable 'sr' [-Wunused-variable]
   44 |   int sr=r;
      |       ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2552 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2552 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 3 ms 2392 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2552 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 3 ms 2392 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 296 ms 26712 KB Output is correct
15 Correct 172 ms 23060 KB Output is correct
16 Correct 267 ms 27064 KB Output is correct
17 Correct 154 ms 17364 KB Output is correct