Submission #310740

#	Time	Username	Problem	Language	Result	Execution time	Memory
310740		ly20	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	665 ms	26856 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10, MOD = 1e9 + 7, P = 29;
string s;
int t;
long long hs[MAXN], pot[MAXN];
long long val(int i, int j) {
    long long resp = hs[i] - (hs[j + 1] * pot[j - i + 1]) % MOD;
    resp += MOD;
    resp %= MOD;
    return resp;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        cin >> s;
        int n = s.size();
        pot[0] = 1;
        for(int i = 1; i <= n; i++) {
            pot[i] = pot[i - 1] * P;
            pot[i] %= MOD;
        }
        hs[n] = 0;
        for(int i = n - 1; i >= 0; i--) {
            hs[i] = hs[i + 1] * P + (s[i] - 'a');
            hs[i] %= MOD;
        }
        int ini1 = 0, fim1 = 0, ini2 = n - 1, fim2 = n - 1;
        int resp = 0;
        while(fim1 < fim2) {
            long long vl1 = val(ini1, fim1), vl2 = val(fim2, ini2);
            if(vl1 == vl2) {
                resp += 2;
                ini1 = fim1 + 1; fim1 = ini1;
                ini2 = fim2 - 1; fim2 = ini2;
            }
            else {
                fim1++; fim2--;
            }
        }
        if(ini1 <= ini2) resp++;
        printf("%d\n", resp);
    }
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

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