Submission #45969

#TimeUsernameProblemLanguageResultExecution timeMemory
45969sorry_BenqPalindromic Partitions (CEOI17_palindromic)C++17
100 / 100
6687 ms105336 KiB
/** * Source: own * Description: Pairs reduce frequency of collision * Verification: Dec 17 Plat 1 */ #pragma GCC optimize("O3") #pragma GCC target("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; template<typename T> ostream& operator<< (ostream& out, const pair<T, T>& v) { out << "{" << v.first << ", " << v.second << "}"; return out; } template<typename T> ostream& operator<< (ostream& out, const vector<T>& v) { out << "["; size_t last = v.size() - 1; for(size_t i = 0; i < v.size(); ++i) { out << v[i]; if (i != last) out << ", "; } out << "]"; return out; } template<typename T> ostream& operator<< (ostream& out, const set<T>& v) { out << "["; auto pen = v.end(); pen--; for (auto it = v.begin(); it != v.end(); it++){ out << *it; if (it != pen){ out << ", "; } } out << "]"; return out; } template<typename T> ostream& operator<< (ostream& out, const Tree<T>& v) { out << "["; auto pen = v.end(); pen--; for (auto it = v.begin(); it != v.end(); it++){ out << *it; if (it != pen){ out << ", "; } } out << "]"; return out; } typedef pair<ll, ll> pll; template<class T> pair<T,T> operator+(const pair<T,T>& l, const pair<T,T>& r) { return {(l.f+r.f)%MOD,(l.s+r.s)%MOD}; } template<class T> pair<T,T> operator-(const pair<T,T>& l, const pair<T,T>& r) { return {(l.f-r.f+MOD)%MOD,(l.s-r.s+MOD)%MOD}; } template<class T> pair<T,T> operator*(const pair<T,T>& l, const T& r) { return {l.f*r%MOD,l.s*r%MOD}; } template<class T> pair<T,T> operator*(const pair<T,T>& l, const pair<T,T>& r) { return {l.f*r.f%MOD,l.s*r.s%MOD}; } struct hsh { string S; vector<pll> po, ipo, cum; pll base = mp(948392576,573928192); ll modpow(ll b, ll p) { return !p?1:modpow(b*b%MOD,p/2)*(p&1?b:1)%MOD; } ll inv(ll x) { return modpow(x,MOD-2); } void gen(string _S) { S = _S; po.resize(sz(S)), ipo.resize(sz(S)), cum.resize(sz(S)+1); po[0] = ipo[0] = {1,1}; FOR(i,1,sz(S)) { po[i] = po[i-1]*base; ipo[i] = {inv(po[i].f),inv(po[i].s)}; } F0R(i,sz(S)) cum[i+1] = cum[i]+po[i]*(ll)(S[i]-'a'+1); } pll get(int l, int r) { return ipo[l]*(cum[r+1]-cum[l]); } }; int lcp(hsh& a, hsh& b) { // can be used to generate a suffix array int lo = 0, hi = min(sz(a.S),sz(b.S)); while (lo < hi) { int mid = (lo+hi+1)/2; if (a.get(0,mid-1) == b.get(0,mid-1)) lo = mid; else hi = mid-1; } return lo; } string s; hsh h; int solve(int idx){ if (s.size() % 2 == 1){ if (idx == s.size() / 2) return 1; int res = 1; for (int j = idx + 1; j <= s.size() / 2; j++){ if (h.get(idx, j - 1) == h.get(s.size() - j, s.size() - 1 - idx)){ return max(res, solve(j) + 2); } } return res; } else{ if (idx == s.size() / 2) return 0; int res = 1; for (int j = idx + 1; j <= s.size() / 2; j++){ if (h.get(idx, j - 1) == h.get(s.size() - j, s.size() - 1 - idx)){ return max(res, solve(j) + 2); } } return res; } } int main() { int T; cin >> T; for (int testcase = 0; testcase < T; testcase++){ cin >> s; h.gen(s); cout << solve(0) << endl; } }

Compilation message (stderr)

palindromic.cpp: In function 'int solve(int)':
palindromic.cpp:148:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (idx == s.size() / 2) return 1;
       ~~~~^~~~~~~~~~~~~~~
palindromic.cpp:150:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = idx + 1; j <= s.size() / 2; j++){
                         ~~^~~~~~~~~~~~~~~
palindromic.cpp:158:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (idx == s.size() / 2) return 0;
       ~~~~^~~~~~~~~~~~~~~
palindromic.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = idx + 1; j <= s.size() / 2; j++){
                         ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...