Submission #955861

#TimeUsernameProblemLanguageResultExecution timeMemory
955861vjudge1Palindromic Partitions (CEOI17_palindromic)C++17
100 / 100
119 ms27792 KiB
#include<bits/stdc++.h> #define INF 1e18 #define fi first #define se second #define FOR(i, k, n) for(int i = k; i <= n; i++) #define FOR1(i, k, n) for(int i = k; i >= n; i--) #define pb push_back #define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define vi vector<int> #define pii pair<int, int> #define vii vector<pii> #define ll long long #define vll vector<ll> #define pll pair<ll, ll> #define re return 0 #define input "AD.inp" #define output "AD.out" #define rf freopen(input, "r", stdin); freopen(output, "w", stdout) using namespace std; const int maxn = 1e6 + 5; const int base = 57; const int mod = 1e9 + 7; ll Hash[maxn]; ll H[maxn]; ll get_hash(int l, int r) { if(l > r) return -1; return (Hash[r] - Hash[l - 1] * H[r - l + 1] + (ll)mod * mod) % mod; } int main() { fastio; H[0] = 1; FOR(i, 1, 1000000) H[i] = (H[i - 1] * base) % mod; int t; cin >> t; while(t--) { string s; cin >> s; int n = s.size(); if(n == 1) { cout << 1 << "\n"; continue; } Hash[0] = 0; s = ' ' + s; FOR(i, 1, n) Hash[i] = (Hash[i - 1] * base + s[i]) % mod; int l = 1, r = n, l1 = 1, r1 = n; int ans = 0; while(l1 < r1) { l1 = l, r1 = r; while(get_hash(l, l1) != get_hash(r1, r) && r1 > l1) { l1++; r1--; } if(l1 < r1) { ans += 2; l = l1 + 1; r = r1 - 1; } else { ans++; break; } if(l > r) break; } cout << ans << "\n"; } re; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...