Submission #45691

#TimeUsernameProblemLanguageResultExecution timeMemory
45691sorry_BenqPalindromic Partitions (CEOI17_palindromic)C++17
60 / 100
10102 ms13800 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<int,int> #define vi vector<int> #define all(a) (a).begin(),(a).end() #define F first #define S second #define sz(x) (int)x.size() #define hell 1000000007 #define endl '\n' using namespace std; const int MAXN=1000005; string s; struct PalindromicTree{ int N,cur; vector<map<int,int>> next; vector<int> link,start,len,diff,slink; PalindromicTree(): N(0),cur(0){ node(); len[0]=-1; node(); } int node(){ next.emplace_back(); link.emplace_back(0); start.emplace_back(0); len.emplace_back(0); diff.emplace_back(0); slink.emplace_back(0); return N++; } void add_letter(int idx){ //cout << s[idx] << endl; while(true){ if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]) break; cur=link[cur]; } if(next[cur].find(s[idx])!=next[cur].end()){ cur=next[cur][s[idx]]; return; } node(); next[cur][s[idx]]=N-1; len[N-1]=len[cur]+2; start[N-1]=idx-len[N-1]+1; if(len[N-1]==1){ link[N-1]=diff[N-1]=slink[N-1]=1; cur=N-1; return; } while(true){ cur=link[cur]; if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]) break; } link[N-1]=next[cur][s[idx]]; diff[N-1]=len[N-1]-len[link[N-1]]; if(diff[N-1]==diff[link[N-1]]) slink[N-1]=slink[link[N-1]]; else slink[N-1]=link[N-1]; cur=N-1; } }; ll dp[MAXN],sans[MAXN]; int main() { int T; cin >> T; for (int testcase = 0; testcase < T; testcase++){ string str; cin>>str; //cout << str << endl; PalindromicTree pt; int i,cur; s.clear(); for(i=0;i<sz(str)/2;i++){ s.pb(str[i]); s.pb(str[sz(str)-i-1]); } if (sz(str) % 2){ s.pb(str[sz(str)/2]); } //cout << s.size() << endl; dp[0]=0; int res = 1; for(i=1;i<=sz(s);i++){ dp[i] = -hell; pt.add_letter(i-1); //cout << i << ' ' << dp[i] << ' ' << pt.cur << endl; int cnt = 0; for(cur=pt.cur;cur>1;cur=pt.link[cur]){ if (pt.len[cur] % 2 == 0){ dp[i] = max(dp[i], dp[i - pt.len[cur]] + 2); } } int cur = dp[i]; if (i != sz(s)) cur++; if (cur > res) res = cur; } cout << res << endl; } }

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:93:8: warning: unused variable 'cnt' [-Wunused-variable]
    int cnt = 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...