Submission #320561

#	Time	Username	Problem	Language	Result	Execution time	Memory
320561		AriaH	Palindromic Partitions (CEOI17_palindromic)	C++11	0 / 100	4 ms	4204 KiB

palindromic

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 1e5 + 10;
const int LOG = 10;

string s;

int rnk[LOG][N], A[N], T, n;

bool cmp(int i, int j)
{
    if(rnk[T - 1][i] == rnk[T - 1][j])
    {
	if(max(i, j) + (1 << (T - 1)) > n) return i > j;
	return rnk[T - 1][i + (1 << (T - 1))] < rnk[T - 1][j + (1 << (T - 1))];
    }
    return rnk[T - 1][i] < rnk[T - 1][j];
}

void B()
{
    for(int i = 1; i <= n; i ++)
    {
	A[i] = i;
	rnk[0][i] = s[i] - 'a' + 1;
    }
    for(T = 1; T < LOG; T ++)
    {
	sort(A + 1, A + n + 1, cmp);
	rnk[T][A[1]] = 1;
	for(int i = 2; i <= n; i ++)
	{
	    rnk[T][A[i]] = rnk[T][A[i - 1]] + cmp(A[i - 1], A[i]);
	}
    }
}

int lcp(int i, int j)
{
    int tot = 0;
    for(T = LOG - 1; ~T; T --)
    {
	if(max(i, j) + (1 << T) - 1 > n || rnk[T][i] != rnk[T][j]) continue;
	tot |= 1 << T;
	i += 1 << T;
	j += 1 << T;
    }
    return tot;
}

int is_eq(int i, int j, int sz)
{
    if(lcp(i, j - sz + 1) >= sz) return 1;
    return 0;
}

inline void solve()
{
    memset(rnk, 0, sizeof rnk);
    cin >> s;
    n = (int)s.size();
    s = "." + s;
    B();
    int l = 1, r = n, ans = 1, sz = 1;
    while(l <= r)
    {
	while(l + sz < n && r - sz + 1 > 0 && !is_eq(l, r, sz)) sz ++;
	if(l + sz - 1 >= r - sz + 1) break;
	if(l + sz == r - sz + 1) { ans ++; break; }
	ans += 2;
	l += sz;
	r -= sz;
    }
    cout << ans << endl;
}

int main()
{
    int q;
    cin >> q;
    while(q--)
    {
	solve();
    }
    return 0;
}
/*!
        stay away from negative people they have a problem for every solution !
*/

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40