Submission #1230639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230639		sunflower	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	10090 ms	13072 KiB

palindromic

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define debug(x) cout << #x << " = " << (x) << endl;

#define fi first
#define se second
#define left    __left
#define right   __right
#define prev    __prev
#define next    __next

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

const int MOD[] = {(int) 1e9 + 2277, (int) 1e9 + 5277};
const int base = 256;
const int NMOD = 1;

struct Hash {
    int value[NMOD];

    Hash() {
        memset(value, 0, sizeof(value));
    }

    bool operator == (const Hash &other) const {
        REP(i, NMOD) if (value[i] != other.value[i]) return false;
        return true;
    }

    bool operator != (const Hash &other) const {
        REP(i, NMOD) if (value[i] != other.value[i]) return true;
        return false;
    }

    bool operator < (const Hash &other) const {
        REP(i, NMOD) if (value[i] != other.value[i]) return value[i] < other.value[i];
        return false;
    }
};

#define MAX_N 1'000'100
string s;
int lenS;

int pw[NMOD][MAX_N + 2], hs[NMOD][MAX_N + 2];
int dp[MAX_N + 2];

void buildHash() {
    REP(j, NMOD) {
        pw[j][0] = 1, hs[j][0] = 0;
        FOR(i, 1, MAX_N) pw[j][i] = 1LL * pw[j][i - 1] * base % MOD[j];
        FOR(i, 1, lenS) hs[j][i] = (hs[j][i - 1] + 1LL * pw[j][i - 1] * s[i]) % MOD[j];
    }
}

Hash getHash(int l, int r) {
    assert(l <= r);
    Hash res;

    REP(i, NMOD) {
        int tmp = hs[i][r] - hs[i][l - 1];
        if (tmp < 0) tmp += MOD[i];
        res.value[i] = 1LL * tmp * pw[i][MAX_N - l + 1] % MOD[i];
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    #define task "test"
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

    int t;
    cin >> t;
    while (t--) {
        cin >> s;
        lenS = SZ(s);
        s = '*' + s;
        buildHash();

        memset(dp, -1, (lenS + 2) * sizeof(int));
        dp[0] = 0;
        FOR(i, 1, lenS >> 1) {
            FOR(j, 1, i) if (dp[j - 1] != -1 && getHash(j, i) == getHash(lenS - i + 1, lenS - j + 1)) {
                maximize(dp[i], dp[j - 1] + 1);
            }
        }

        int ans = 1;
        FOR(i, 1, lenS >> 1) {
            int tmp = dp[i] * 2;
            if (2 * i < lenS) ++tmp;
            maximize(ans, tmp);
        }

        cout << ans << "\n";
    }

    return 0;
}

Compilation message (stderr)

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

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