Submission #1095074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095074		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	140 ms	50260 KiB

palindromic

//------------------------------------\
//   ------------------------------   \
//  |    created by Pham Phuongg   |  \
//  |       phamvuphuong2008       |  \
//  |     THPT CHUYEN HA TINH      |  \
//  |      HA TINH, VIET NAM       |  \
//  |    Bé Phương from TK4-CHT    |  \
//   ------------------------------   \
//------------------------------------\

#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
//#define ii pair<int ,int >
#define endl '\n'
#define iii pair<int,ii>
#define pb push_back
#define task "main"
#define base 145443351LL
using namespace std;
const int maxn = 1e6+5;
const int lim = 1e6;
long long mod = 1e9+7;
long long pot[maxn], Hash[maxn], n;
string s;

 bool compare(int i, int j, int ii, int jj) {
    long long dx = (i > 0 ? Hash[i - 1] : 0);
    long long A = (mod + Hash[j] - dx) % mod;
    
    long long dx2 = (ii > 0 ? Hash[ii - 1] : 0);
    long long A2 = (mod + Hash[jj] - dx2) % mod;
    
    return (((A * pot[ii]) % mod) == ((A2 * pot[i]) % mod));
}

int dq(int ini) {
    int fim = s.size() - 1 - ini;

    if (ini == fim) return 1;

    if (ini > fim) return 0;

    int best = 1;

    for (int p = ini; p <= (ini + fim) / 2; p++) {
        if (compare(ini, p, fim - p + ini, fim)) {
            best = max(best, 2 + dq(p + 1));
            break;
        }
    }

    return best;
}

void solve() {
    cin >> s;
    n = s.length();
    
    Hash[0] = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0) Hash[i] = Hash[i - 1];
        Hash[i] = (Hash[i] + s[i] * pot[i]) % mod;
    }
    cout << dq(0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    if (fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    
    pot[0] = 1;
    for (int i = 1; i <= lim; i++) pot[i] = (pot[i - 1] * base) % mod;

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
        cout << endl;
    }
}

Compilation message (stderr)

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

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