oj.uz

Submission #318150

# Submission time Handle Problem Language Result Execution time Memory
318150 2020-10-31T14:21:20 Z RohamIzadidoost Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 10000 ms 17572 KB 
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
typedef long long ll ;
#define pll pair<ll , ll >
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
using namespace std;
const int maxn = 1000*1000+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1000696969 ;
const ll mod2 = 1e9 + 7 ; 
const ll H = 1777013 ;
string s  ; 
ll pt[maxn] , h[maxn]  , L , R , sz , n  , l, r  , mid , b   , ans  ;

ll hsh(int l , int r){
	if(l == 0 ) return h[r] ; 
	return ( h[r] - h[l-1] * pt[r-l+1] % mod  + mod ) % mod ;  }
 
bool check(int x){
	return( hsh(L , L + x - 1) == hsh(R - x + 1 , R) ) ; 
}
int Main()
{
	ans = 0 ; 
	cin>>s ; n = s.size() ; 
	h[0] = s[0] ; 
	for(int i = 1 ; i < n ; i ++ ){
		h[i] = h[i-1] * H % mod + s[i] ; 
		h[i] %= mod ; 
	}
	L= 0 , R = n - 1 ;  
	while(n){
		l = 0 , r = n/2 + 1 , b = 1 ; 
		while(r-l>1){
			mid = (l + r)/ 2 ; 
			if(check(mid)) l = mid , b = 0 ; 
			else r = mid ; 
		}
		if(b){
			n = 0 ; 
			ans ++ ; 
		}else{
			L += l ; 
			R -= l ;
			ans += 2 ; 
			n -= 2 * l ;  
		}
	}
	cout<<ans << endl ; 
}

int main()
{
	int t ; 
	migmig; 
	pt[0] = 1 ; 
	for(int i = 1; i < maxn ; i ++ )
	{
		pt[i] = pt[i-1] * H % mod ; 
	}
	cin>> t ; 
	while(t--)
	{
		Main() ; 
	}
}

Compilation message

palindromic.cpp: In function 'int Main()':
palindromic.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10014 ms 17572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10014 ms 17572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10014 ms 17572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10014 ms 17572 KB Time limit exceeded
2 Halted 0 ms 0 KB -