oj.uz

Submission #448647

# Submission time Handle Problem Language Result Execution time Memory
448647 2021-07-31T10:26:33 Z Khizri Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 113 ms 20608 KB 
#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1712429437)
#define endl "\n"
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
	if(a>b) swap(a,b);
	if(a==0) return a+b;
	return gcd(b%a,a);
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
bool is_prime(ll n){
	ll k=sqrt(n);
	if(n==2) return true;
	if(n<2||n%2==0||k*k==n) return false;
	for(int i=3;i<=k;i+=2){
		if(n%i==0){
			return false;
		}
	}
	return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=1e6+5;
ll t=1,p[mxn];
map<char,ll>mp;
void f(){
	p[0]=1;
	for(int i=1;i<=1e6;i++){
		p[i]=(p[i-1]*26)%MOD;
	}
	ll k=0;
	for(char i='a';i<='z';i++){
		mp[i]=++k;
	}
}
void solve(){
	string s;
	cin>>s;
	ll x=0,y=0,l=0,r=s.size()-1,l1=0,r1=s.size()-1;
	ll ans=0;
	while(l<r){
		x=((x*26)%MOD+mp[s[l]])%MOD;
		y=((p[(r1-r)]*mp[s[r]])%MOD+y)%MOD;
		l++,r--;
		if(x==y){
			ans+=2;
			x=0,y=0;
			r1=r;
		}
	}
	if(l==r||x>0||y>0){
		ans++;
	}
	cout<<ans<<endl;
}
int main(){
	IOS;
	f();
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Compilation message

palindromic.cpp: In function 'void solve()':
palindromic.cpp:58:30: warning: unused variable 'l1' [-Wunused-variable]
   58 |  ll x=0,y=0,l=0,r=s.size()-1,l1=0,r1=s.size()-1;
      |                              ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 9 ms 8012 KB Output is correct
3 Correct 9 ms 8140 KB Output is correct
4 Correct 9 ms 8012 KB Output is correct
5 Correct 9 ms 8136 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 9 ms 8012 KB Output is correct
3 Correct 9 ms 8140 KB Output is correct
4 Correct 9 ms 8012 KB Output is correct
5 Correct 9 ms 8136 KB Output is correct
6 Correct 10 ms 8140 KB Output is correct
7 Correct 9 ms 8024 KB Output is correct
8 Correct 9 ms 8140 KB Output is correct
9 Correct 11 ms 8140 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 9 ms 8012 KB Output is correct
3 Correct 9 ms 8140 KB Output is correct
4 Correct 9 ms 8012 KB Output is correct
5 Correct 9 ms 8136 KB Output is correct
6 Correct 10 ms 8140 KB Output is correct
7 Correct 9 ms 8024 KB Output is correct
8 Correct 9 ms 8140 KB Output is correct
9 Correct 11 ms 8140 KB Output is correct
10 Correct 10 ms 8140 KB Output is correct
11 Correct 9 ms 8156 KB Output is correct
12 Correct 11 ms 8208 KB Output is correct
13 Correct 10 ms 8140 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 9 ms 8012 KB Output is correct
3 Correct 9 ms 8140 KB Output is correct
4 Correct 9 ms 8012 KB Output is correct
5 Correct 9 ms 8136 KB Output is correct
6 Correct 10 ms 8140 KB Output is correct
7 Correct 9 ms 8024 KB Output is correct
8 Correct 9 ms 8140 KB Output is correct
9 Correct 11 ms 8140 KB Output is correct
10 Correct 10 ms 8140 KB Output is correct
11 Correct 9 ms 8156 KB Output is correct
12 Correct 11 ms 8208 KB Output is correct
13 Correct 10 ms 8140 KB Output is correct
14 Correct 113 ms 20608 KB Output is correct
15 Correct 69 ms 15588 KB Output is correct
16 Correct 98 ms 19680 KB Output is correct
17 Correct 71 ms 14708 KB Output is correct