Submission #955646

#	Time	Username	Problem	Language	Result	Execution time	Memory
955646		Yang8on	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	105 ms	28568 KiB

palindromic

#include <bits/stdc++.h>
#define gsn "Palindromic Partitions"
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r) (rng);
}

const int maxn = 1000005;
const int base = 31;
const ll mod = 1000000003ll;

ll Hash[maxn], Pow[maxn];
ll get(int i, int j)
{
    return (Hash[j] - Hash[i - 1] * Pow[j - i + 1] + mod * mod) % mod;
}

void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    s = ' ' + s;

    Pow[0] = 1;
    fi(i, 1, n)
    {
        Pow[i] = Pow[i - 1] * base % mod;
        Hash[i] = (Hash[i - 1] * base + s[i] - 'a' + 1) % mod;
    }

    int vt1 = 1, vt2 = n, ans = 0;
    for(int i = 1; i <= vt2; i ++)
    {
        if(get(vt1, i) == get(vt2 - (i - vt1), vt2))
        {
            if(i < vt2 - (i - vt1)) ans += 2;
            else ans += 1;
            vt2 = vt2 - (i - vt1) - 1, vt1 = i + 1;
        }

    }
    if(vt1 <= vt2) ans ++;
    cout << ans << '\n';
}


int main()
{
    if(fopen(gsn".inp", "r"))
    {
        freopen(gsn".inp", "r", stdin);
        freopen(gsn".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int nTest = 1;
    cin >> nTest;

    while(nTest --)
    {
        solve();
    }




    /// ------------------check time!-----------------///
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(gsn".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(gsn".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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