Submission #398198

#TimeUsernameProblemLanguageResultExecution timeMemory
398198fun_dayPalindromic Partitions (CEOI17_palindromic)C++14
60 / 100
10045 ms5920 KiB
#include <bits/stdc++.h> using namespace std; #define debug(x) cerr << " - " << #x << ": " << x << '\n'; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << '\n'; #define debugv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << " ,"; cerr << ']' << "\n"; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; while(tt--){ string ss ; cin >> ss ; int n = ss.length(); map<char, vector<int>>mp; for(int i = 0 ; i < n; i++){ mp[ss[i]].push_back(i); } int ans = 1; for(int i = n-1,qs = 0 ; qs< n/2 ; i--,qs++){ char q = ss[i]; string acc; string against; bool is = 1; int idx = qs; for(int j = 0 ; j < (int)mp[q].size() ; j++){ if(mp[q][j]<idx){ mp[q].erase(mp[q].begin()); j--; continue; } if(mp[q][j]>=n/2)break; acc += ss.substr(idx , mp[q][j]-idx+1); int rs = acc.length(); against = ss.substr(i-rs+1 , rs); idx = mp[q][j]+1; if(against == acc){ acc.clear(); ans+=2; against.clear(); i =i-rs+1; qs = mp[q][j]; if(qs+1==i)ans--; mp[q].erase(mp[q].begin()); is = 0; break; } mp[q].erase(mp[q].begin()); j--; } if(is)break; } cout << ans << '\n'; cout.flush(); } 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...