Submission #62711

#	Time	Username	Problem	Language	Result	Execution time	Memory
62711		eriksuenderhauf	Palindromic Partitions (CEOI17_palindromic)	C++11	100 / 100	364 ms	33012 KiB

palindromic

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <fstream>
#define ni(n) scanf("%d", &n)
#define nl(n) scanf("%I64d", &n)
#define nai(a,n) for (int i = 0; i < (n); i++) ni((a)[i])
#define nal(a,n) for (int i = 0; i < (n); i++) nl((a)[i])
#define case(t) printf("Case #%d: ", (t))
#define pii pair<int, int>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
typedef long long ll;
const double pi = acos(-1);
const ll MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
const int pr1 = 137;
const int pr2 = 2017;
using namespace std;
ll h1[MAXN], h2[MAXN];
ll power[2][MAXN];
char str[MAXN];

ll binpow(ll a, ll b)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        b /= 2ll;
    }
    return ret;
}

ll _h1(int a, int b)
{
    if (a < 0)
        return h1[b];
    ll tmp = (h1[a] * power[0][b - a]) % MOD;
    return (h1[b] - tmp + MOD) % MOD;
}

ll _h2(int a, int b)
{
    if (a < 0)
        return h2[b];
    ll tmp = (h2[a] * power[1][b - a]) % MOD;
    return (h2[b] - tmp + MOD) % MOD;
}

void solve()
{
    scanf("%s", str);
    int n = strlen(str);
    h1[0] = h2[0] = str[0];
    for (int i = 1; i < n; i++)
    {
        h1[i] = (str[i] + h1[i - 1] * pr1 % MOD) % MOD;
        h2[i] = (str[i] + h2[i - 1] * pr2 % MOD) % MOD;
    }
    int l = -1, r = n - 1, ans = 1;
    for (int i = 0; i < n - 1 - i; i++)
    {
        if (_h1(l, i) == _h1(n - 2 - i, r) && _h2(l, i) == _h2(n - 2 - i, r))
        {
            ans += 2;
            l = i;
            r = n - 2 - i;
        }
    }
    if (l == r)
        --ans;
    printf("%d\n", ans);
}

int main()
{
    power[0][0] = power[1][0] = 1;
    for (int i = 1; i < MAXN; i++)
        power[0][i] = (power[0][i - 1] * pr1) % MOD,
        power[1][i] = (power[1][i - 1] * pr2) % MOD;
    int t;
    ni(t);
    while (t--)
        solve();
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str);
     ~~~~~^~~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &n)
               ~~~~~^~~~~~~~~~
palindromic.cpp:95:5: note: in expansion of macro 'ni'
     ni(t);
     ^~

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