Submission #309488

#TimeUsernameProblemLanguageResultExecution timeMemory
309488Kenzo_1114Palindromic Partitions (CEOI17_palindromic)C++17
0 / 100
10 ms8192 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 1000010; const long long int MOD = 1e9 + 19; int t; long long int p[MAXN], sp[MAXN]; string s; void init() { p[0] = 1; for(int i = 1; i < MAXN; i++) p[i] = (p[i - 1] * 23) % MOD; } long long int Hash(int i, int j) { long long int h = (sp[j] - sp[i - 1] + MOD) * p[i]; return h % MOD; } void solve() { cin >> s; int sz = (int) s.size(); for(int i = 0; i < sz; i++) { sp[i] = (p[sz - i - 1] * (s[i] - 'a')) % MOD; if(i) sp[i] = (sp[i - 1] + sp[i]) % MOD; } int l = 0, r = sz - 1, ans = 0; while(l <= r) { if(l == r) ans--; if(s[l] == s[r]) l++, r--; else for(int k = 1; k <= sz; k++) if(Hash(l, l + k) == Hash(r - k, r)) { l += k + 1, r -= k + 1; if(r < l) ans--; break; } ans += 2; } printf("%d\n", ans); } int main () { init(); scanf("%d", &t); while(t--) solve(); }

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...