Submission #320555

#	Time	Username	Problem	Language	Result	Execution time	Memory
320555		AriaH	Palindromic Partitions (CEOI17_palindromic)	C++11	0 / 100	235 ms	131072 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 = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

char S[N];

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);
    scanf("%s", &S);
    s = S;
    n = (int)s.size();
    s = "." + s;
    B();
    int l = 1, r = n, ans = 1, sz = 1;
    while(l <= r)
    {
	while(!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;
    }
    printf("%d\n", ans);
}

int main()
{
    int q;
    scanf("%d", &q);
    while(q--)
    {
	solve();
    }
    return 0;
}
/*!
        stay away from negative people they have a problem for every solution !
*/

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:83:13: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000010]' [-Wformat=]
   83 |     scanf("%s", &S);
      |            ~^
      |             |
      |             char*
palindromic.cpp: In function 'int main()':
palindromic.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
palindromic.cpp: In function 'void solve()':
palindromic.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |     scanf("%s", &S);
      |     ~~~~~^~~~~~~~~~

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