Submission #164439

#TimeUsernameProblemLanguageResultExecution timeMemory
164439kungfulonPalindromic Partitions (CEOI17_palindromic)C++14
0 / 100
3 ms1144 KiB
///Phạm Nguyễn Tuấn Hoàng/// #include <bits/stdc++.h> #define rep(i,a,b) for(int i = (a);i <= (b);i++) #define repd(i,a,b) for(int i = (a);i >= (b);i--) #define F first #define S second #define PB push_back #define Task "" using namespace std; //template <class T> inline read(T &a){a = 0;char c;bool nega = 0;while(!isdigit(c = getchar()) && c != '-');if(c == '-') nega = 1,c = getchar();a = c - 48;while(isdigit(c = getchar()))a = a * 10 + c - 48;if(nega) a = -a;} //template <class T> inline writep(T a){if(a > 9) writep(a / 10);putchar(a % 10 + 48);} //template <class T> inline write(T a){if(a < 0) putchar('-'),a = -a;writep(a);putchar(' ');} //template <class T> inline writeln(T a){write(a);putchar('\n');} const int base = 1000000007; unsigned long long Hash[100012],h[100012]; int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // freopen(Task".inp","r",stdin); // freopen(Task".out","w",stdout); h[0] = 1; rep(i,1,100000) h[i] = h[i-1] * base; int T; cin >> T; while(T--) { string s; cin >> s; int n = s.size(); s = ' ' + s; int End = n,Begin = 1,cnt = 0,lastEnd = n + 1; vector<int> df(27),ds(27); while(End > Begin) { bool check = 1; Hash[Begin] = Hash[Begin - 1] * base + s[Begin]; Hash[End] = Hash[End + 1] + h[lastEnd - End - 1] * s[End]; if(Hash[End] != Hash[Begin]) check = 0; if(check) { cnt += 2; rep(i,0,'z' - 'a') df[i] = ds[i] = 0; lastEnd = End; Hash[Begin] = Hash[End] = 0; } End--,Begin++; } cout << cnt + (lastEnd != Begin) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...