oj.uz

Submission #955649

# Submission time Handle Problem Language Result Execution time Memory
955649 2024-03-31T08:44:37 Z thunopro Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 130 ms 11624 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 1000009 
#define ll long long 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 
#define TIME (1.0*clock()/TIME_PERS_SEC) 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ;} 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ;} 

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

mt19937 rng(time(0)) ; 

string s ;
int hashA [maxn] ; 
int Pow [maxn] ; 

int get_hashA ( int l , int r ) 
{
	return (hashA[r]-1ll*hashA[l-1]*Pow[r-l+1]%mod+1ll*mod*mod)%mod ; 
}
int solve ( int l , int r ) 
{
	if ( l == r ) return 1 ; 
	if ( l > r ) return 0 ; 
	for ( int i = 0 ; l+i < r-i ; i ++ ) 
	{
		if ( get_hashA (l,l+i) == get_hashA (r-i,r) ) return 2 + solve (l+i+1,r-i-1) ; 
	}
	return 1 ; 
}

int main ()
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0);cout.tie(0); 
//	rf () ; 
	Pow [0] = 1 ; 
	for ( int i = 1 ; i < maxn ; i ++ ) Pow [i] = 1ll*Pow[i-1]*53%mod ; 
	int test ; cin >> test ; 
	while ( test -- ) 
	{
		cin >> s ;
		int n = s.size () ; 
		s = ' ' + s ; 
		for ( int i = 1 ; i <= n ; i ++ ) hashA [i] = (1ll*hashA[i-1]*53+s[i])%mod ; 
		cout << solve (1,n) << "\n" ; 
	}
}

Compilation message

palindromic.cpp: In function 'void rf()':
palindromic.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4700 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 6 ms 4700 KB Output is correct
5 Correct 7 ms 5252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4700 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 6 ms 4700 KB Output is correct
5 Correct 7 ms 5252 KB Output is correct
6 Correct 6 ms 4696 KB Output is correct
7 Correct 7 ms 4732 KB Output is correct
8 Correct 6 ms 4696 KB Output is correct
9 Correct 6 ms 4700 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4700 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 6 ms 4700 KB Output is correct
5 Correct 7 ms 5252 KB Output is correct
6 Correct 6 ms 4696 KB Output is correct
7 Correct 7 ms 4732 KB Output is correct
8 Correct 6 ms 4696 KB Output is correct
9 Correct 6 ms 4700 KB Output is correct
10 Correct 8 ms 4696 KB Output is correct
11 Correct 7 ms 4696 KB Output is correct
12 Correct 7 ms 4744 KB Output is correct
13 Correct 8 ms 4700 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4700 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 6 ms 4700 KB Output is correct
5 Correct 7 ms 5252 KB Output is correct
6 Correct 6 ms 4696 KB Output is correct
7 Correct 7 ms 4732 KB Output is correct
8 Correct 6 ms 4696 KB Output is correct
9 Correct 6 ms 4700 KB Output is correct
10 Correct 8 ms 4696 KB Output is correct
11 Correct 7 ms 4696 KB Output is correct
12 Correct 7 ms 4744 KB Output is correct
13 Correct 8 ms 4700 KB Output is correct
14 Correct 130 ms 10224 KB Output is correct
15 Correct 76 ms 10240 KB Output is correct
16 Correct 121 ms 11624 KB Output is correct
17 Correct 71 ms 7808 KB Output is correct