Submission #1226111

#TimeUsernameProblemLanguageResultExecution timeMemory
1226111theiuliusPalindromic Partitions (CEOI17_palindromic)C++20
100 / 100
102 ms18924 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ff first #define ss second #define pb push_back // #define endl "\n" const int MOD = 1e9 + 7, N = 1e6 + 6; int n; main(){ /*ifstream cin(".in"); ofstream cout(".out");*/ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int myp[N] = {1}; for (int i = 1; i < N; i++){ myp[i] = (myp[i - 1] * 31) % MOD; } cin >> n; for (int k = 0; k < n; k++){ string s; cin >> s; int pre[s.size()] = {}; pre[0] = s[0] - 'a'; int num = 1; for (int i = 1; i < s.size(); i++){ num *= 31; num %= MOD; // cout << ((s[i] - 'a') * num) << endl; pre[i] = (pre[i - 1] + (s[i] - 'a') * num) % MOD; } int last = 0, ans = 0; for (int i = 0; i < s.size() / 2; i++){ int a = pre[i]; if (last){ a -= pre[last - 1] - MOD; a %= MOD; } int b = (pre[s.size() - 1 - last] - pre[s.size() - 2 - i] + MOD) % MOD; int h = s.size() - 1 - last - i; a *= myp[h]; a %= MOD; if (a == b){ ans++; last = i + 1; } } ans *= 2; if (s.size() % 2 || last != s.size() / 2){ ans++; } cout << ans << endl; } }

Compilation message (stderr)

palindromic.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...