Submission #1199893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199893		badge881	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	1027 ms	10200 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int inf = 1e17, N = 2e6 + 1, MOD = (1LL << 61) - 1, B = 23;

int add(int x, int y)
{
    return ((x + y >= MOD) ? (x + y - MOD) : (x + y));
}

int mult(__int128_t x, __int128_t y)
{
    return (x * y) % MOD;
}

int expo(int x, int y)
{
    if (!y)
        return 1;
    int e = expo(x, y / 2);
    e = mult(e, e);
    if (y & 1)
        e = mult(e, x);
    return e;
}

struct Hash
{
    vector<int> roll;
    int n;
    Hash(string &s)
    {
        n = s.size();
        roll.resize(n + 1);
        for (int i = 1; i <= n; i++)
            roll[i] = add(s[i - 1], mult(B, roll[i - 1]));
    }

    int get(int l, int r)
    {
        if (l == 1)
            return roll[r];
        return add(roll[r], MOD - mult(expo(B, r - l + 1), roll[l - 1]));
    }
};
void solve()
{
    char buff[1'000'001];
    scanf("\n%s\n", buff);
    string s = buff;
    int n = s.size();
    int ptr = 1, ptr2 = n;
    int ans = 0;
    Hash h(s);
    bool end = 0;
    while (true)
    {
        bool found = 0;
        int p = ptr, p2 = ptr2;
        for (; ptr < ptr2; ptr++, ptr2--)
            if (h.get(ptr2, p2) == h.get(p, ptr))
            {
                ans += 2;
                if (ptr == ptr2 - 1)
                    end = 1;
                ptr++, ptr2--;
                found = 1;
                break;
            }

        if (!found)
            break;
    }
    if (!end)
        ans++;
    printf("%lld\n", ans);
}

signed main()
{
    int t;
    scanf("%lld", &t);
    while (t--)
        solve();
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("\n%s\n", buff);
      |     ~~~~~^~~~~~~~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%lld", &t);
      |     ~~~~~^~~~~~~~~~~~

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