oj.uz

답안 #318436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318436 2020-11-01T19:37:32 Z soroush Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 1 ms 364 KB 
/*
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn  = 3e6;
const ll mod =1e9+7;
const ll mods [] = {(ll)1e9+7 , (ll)1e9+9 , 696969569 , 177013 , 9699691};
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

struct hsh{
	string s;
	ll n;
	vector < ll > h;
	vector < ll > p;
	ll base;
	ll mod;
	hsh (string S){
		s = S;
		n = s.size();
		h.reserve(n+100);
		base = rng()%100 + 50;
		mod = mods[rng()%5];
		p.pb(1);
		for(int i = 1 ; i < n + 50 ; i ++)
			p.pb((p.back() * base)%mod);
	}
	void calc(){
		ll cur = 0;
		h.pb(cur);
		for(int i = 0 ; i < n ; i ++){
			cur = (cur * base)%mod;
			cur += s[i] - 'a' + 1;
			cur%=mod;
			h.pb(cur);
		}
	}
	ll get(ll l , ll r){
		ll res = h[r];
		res -= (h[l-1]*p[r-l+1])%mod;
		res%=mod;
		res+=mod;
		return(res%mod);
	}
};

int t;
string s;

int32_t main(){
    migmig;
	cin >> t;
	while(t -- ){
		cin >> s;
		hsh h(s);
		h.calc();
		int n = s.size();
		int l = 1 , r = n ;
		int ans = 0;
		while (l!=r){
			bool ok = 0;
			for(int i = l ; i < r ; i ++){
				if(i >= r-i+l)
					break;
				if(h.get(l , i) == h.get(r - i+l , r)){
					ans += 2;
					r = r - i + l-1;
					l = i+1;
					ok = 1;
					break;
				}
			}
			if(!ok or (ok and l == r))
				ans ++ , l = r;
		}
		if(ans==0)ans++;
		cout << ans << endl;
	}




    return(0);
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -