oj.uz

Submission #499722

# Submission time Handle Problem Language Result Execution time Memory
499722 2021-12-29T10:33:30 Z codr0 Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 2058 ms 28580 KB 
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
#define int long long
 
using namespace std;
const int MOD=98765431;
const int M=31;
	
	int pw(int a,int b){
		if(!b) return 1;
		int rt=pw(a,b/2);
		rt=(rt*rt)%MOD;
		if(b&1) rt=(rt*a)%MOD;
		return rt;
	}

	int inv(int x){
		return pw(x,MOD-2);
	}
	
	void Main(){
		int n;
		string s; cin>>s; n=SZ(s); s='$'+s;
		int ps[n+1]={};
		int PW[n+1];
		PW[0]=1;
		FOR(i,1,n) PW[i]=(PW[i-1]*M)%MOD;
		FOR(i,1,n){
			ps[i]=ps[i-1];
			ps[i]=(ps[i]+(((s[i]-'a'+1)*PW[i-1])%MOD))%MOD;
		}
		int l=1,r=n;
		int ans=0;
		while(r>l){
			int mid1=(r+l)/2;
			int mid2=mid1+1;
			if((r-l+1)&1)	mid1--;
			int t=-1;
			FOR(i,0,mid1-l){
				int hsh1=ps[i+l]-ps[l-1];
				hsh1=hsh1*inv(PW[l-1]); hsh1=((hsh1%MOD)+MOD)%MOD;
				int hsh2=ps[r]-ps[r-i-1];
				hsh2=hsh2*inv(PW[r-i-1]); hsh2=((hsh2%MOD)+MOD)%MOD;
				if(hsh1==hsh2) {t=i; break;}
			}
			if(t==-1) {
				ans++;
				break;
			}else{
				l=l+t+1;
				r=r-t-1;
				ans+=2;
			}
		}
		if(r==l) ans++;
		cout<<ans<<'\n';
	}

	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int T; cin>>T;
	while(T--) Main();

	return 0;
    }

Compilation message

palindromic.cpp: In function 'void Main()':
palindromic.cpp:43:8: warning: unused variable 'mid2' [-Wunused-variable]
   43 |    int mid2=mid1+1;
      |        ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 21 ms 492 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 20 ms 544 KB Output is correct
13 Correct 17 ms 460 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 21 ms 492 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 20 ms 544 KB Output is correct
13 Correct 17 ms 460 KB Output is correct
14 Correct 2058 ms 28580 KB Output is correct
15 Correct 1109 ms 23428 KB Output is correct
16 Correct 1925 ms 27508 KB Output is correct
17 Correct 1108 ms 15320 KB Output is correct