Submission #320596

#TimeUsernameProblemLanguageResultExecution timeMemory
320596AriaHPalindromic Partitions (CEOI17_palindromic)C++11
0 / 100
1 ms364 KiB
/** I can do this all day **/ #pragma GCC optimize("O2") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define all(x) (x).begin(),(x).end() #define F first #define S second #define Mp make_pair #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout); #define endl "\n" const int N = 1e5 + 10; const int LOG = 24; string s; ll pw[2][N], Hsh[2][N], mod[2], base = 737, n; pll baze(ll l, ll r) { return Mp((Hsh[0][r] - ((Hsh[0][l - 1] * pw[0][r - l + 1]) % mod[0]) + mod[0]) % mod[0], (Hsh[1][r] - (Hsh[1][l - 1] * pw[1][r - l + 1] % mod[1]) + mod[1]) % mod[1]); } int is_eq(int l, int r, int sz) { if(baze(l, l + sz - 1) == baze(r - sz + 1, r)) return 1; return 0; } void B() { pw[0][0] = pw[1][0] = 1; for(int i = 1; i <= n; i ++) { for(int j = 0; j < 2; j ++) { pw[j][i] = (pw[j][i - 1] * base) % mod[j]; Hsh[j][i] = (Hsh[j][i - 1] * base + s[i] - 'a' + 1) % mod[j]; } } } inline void solve() { cin >> s; n = (int)s.size(); s = "." + s; B(); int l = 1, r = n, ans = 1, sz = 1; while(l <= r) { while(l + sz < n && r - sz + 1 > 0 && !is_eq(l, r, sz)) sz ++; if(l + sz - 1 >= r - sz + 1) break; if(l + sz == r - sz + 1) { ans ++; break; } ans += 2; l += sz; r -= sz; } cout << ans << endl; } int main() { mod[0] = 1e9 + 7; mod[1] = 1e9 + 9; int q; cin >> q; while(q--) { solve(); } return 0; } /*! stay away from negative people they have a problem for every solution ! */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...