Submission #229659

# Submission time Handle Problem Language Result Execution time Memory
229659 2020-05-05T18:01:26 Z tatyam Palindromes (APIO14_palindrome) C++17
100 / 100
654 ms 53280 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using pcc = pair<char, char>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using tuplis = array<ll, 3>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
const ll LINF=0x1fffffffffffffff;
const ll MINF=0x7fffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
const int MODD=998244353;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const ld PI=3.1415926535897932;
const ll dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
const ll dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i=(n);i--;)
#define rrep2(i,n) for(ll i=(n);i--;)
#define rrep3(i,a,b) for(ll i=(b);i-->(a);)
#define rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i:a)
#define all1(i) begin(i),end(i)
#define all2(i,a) begin(i),begin(i)+a
#define all3(i,a,b) begin(i)+a,begin(i)+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(i) (i).rbegin(),(i).rend()
#define rall2(i,k) (i).rbegin(),(i).rbegin()+k
#define rall3(i,a,b) (i).rbegin()+a,(i).rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
#define dsum(...) accumulate(all(__VA_ARGS__),0.0L)
#define elif else if
#define unless(a) if(!(a))
#define mp make_pair
#define mt make_tuple
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define Sort(a) sort(all(a))
#define Rev(a) reverse(all(a))
#define Uniq(a) sort(all(a));a.erase(unique(all(a)),end(a))
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }
inline ll popcnt(ull a){ return __builtin_popcountll(a); }
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
vector<ll> iota(ll n){ vector<ll> a(n); iota(a.begin(), a.end(), 0); return a; }
vector<pll> factor(ull x){ vector<pll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
map<ll,ll> factor_map(ull x){ map<ll,ll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans[i] = 1; while((x /= i) % i == 0) ans[i]++; } if(x != 1) ans[x] = 1; return ans; }
vector<uint> divisor(uint x){ vector<uint> ans; for(uint i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
template<class T> unordered_map<T, ll> press(vector<T>& a){ auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); unordered_map<T, ll> ans; rep(b.size()) ans[b[i]] = i; each(i, a) i = ans[i]; return ans; }
template<class T> map<T, ll> press_map(vector<T>& a){ auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); map<T, ll> ans; rep(b.size()) ans[b[i]] = i; each(i, a) i = ans[i]; return ans; }
int scan(){ return getchar(); }
void scan(int& a){ scanf("%d", &a); }
void scan(unsigned& a){ scanf("%u", &a); }
void scan(long& a){ scanf("%ld", &a); }
void scan(long long& a){ scanf("%lld", &a); }
void scan(unsigned long long& a){ scanf("%llu", &a); }
void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
void scan(float& a){ scanf("%f", &a); }
void scan(double& a){ scanf("%lf", &a); }
void scan(long double& a){ scanf("%Lf", &a); }
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
void print(){ putchar(' '); }
void print(bool a){ printf("%d", a); }
void print(int a){ printf("%d", a); }
void print(unsigned a){ printf("%u", a); }
void print(long a){ printf("%ld", a); }
void print(long long a){ printf("%lld", a); }
void print(unsigned long long a){ printf("%llu", a); }
void print(char a){ printf("%c", a); }
void print(char a[]){ printf("%s", a); }
void print(const char a[]){ printf("%s", a); }
void print(float a){ printf("%.15f", a); }
void print(double a){ printf("%.15f", a); }
void print(long double a){ printf("%.15Lf", a); }
void print(const string& a){ for(auto&& i : a) print(i); }
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
#ifdef DEBUG
inline int __lg(int __n){ return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
#define debug(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
#else
#define debug(...) void(0)
#endif
int first(bool i = true){ return out(i?"first":"second"); }
int yes(bool i = true){ return out(i?"yes":"no"); }
int Yes(bool i = true){ return out(i?"Yes":"No"); }
int No(){ return out("No"); }
int YES(bool i = true){ return out(i?"YES":"NO"); }
int NO(){ return out("NO"); }
int Yay(bool i = true){ return out(i?"Yay!":":("); }
int possible(bool i = true){ return out(i?"possible":"impossible"); }
int Possible(bool i = true){ return out(i?"Possible":"Impossible"); }
int POSSIBLE(bool i = true){ return out(i?"POSSIBLE":"IMPOSSIBLE"); }
void Case(ll i){ printf("Case #%lld: ", i); }


vector< int > manacher(const string &s) {
  vector< int > radius(s.size());
  int i = 0, j = 0;
  while(i < s.size()) {
    while(i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j]) {
      ++j;
    }
    radius[i] = j;
    int k = 1;
    while(i - k >= 0 && i + k < s.size() && k + radius[i - k] < j) {
      radius[i + k] = radius[i - k];
      ++k;
    }
    i += k;
    j -= k;
  }
  return radius;
}
const unsigned bases[64] = {257,262,266,275,276,281,285,290,296,302,306,310,311,313,323,333,344,345,350,357,367,370,373,402,423,425,431,440,442,443,454,457,458,462,471,478,481,487,489,492,499,501,502,503,506,514,524,532,535,541,550,552,557,559,562,563,567,570,571,580,592,597,604,612};
const ull mod = 0x1fffffffffffffff, base = bases[chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now().time_since_epoch()).count() & 63];
struct RollingHash {
    vector<ull> hashed, power;
    
    static constexpr ull mask(int a) { return (1ull << a) - 1; }
    
    inline ull mul(ull a, ull b) const {
        //*
        __uint128_t ans = __uint128_t(a) * b;
        /*/
         // without __uint128_t
         ull a31 = a >> 31, b31 = b >> 31;
         a &= mask(31);
         b &= mask(31);
         ull x = a * b31 + b * a31;
         ull ans = (a31 * b31 << 1) + (x >> 30) + ((x & mask(30)) << 31) + a * b;
         //*/
        ans = (ans >> 61) + (ans & mask(61));
        if(ans >= mod) ans -= mod;
        return ans;
    }
    
    
    RollingHash(const string &s) {
        ll n = s.size();
        hashed.assign(n + 1, 0);
        power.assign(n + 1, 0);
        power[0] = 1;
        rep(n) {
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = mul(hashed[i], base) + s[i];
            if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
        }
    }
    
    ull get(ll l, ll r) const {
        ull ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
        if(ret >= mod) ret -= mod;
        return ret;
    }
    
    ull connect(ull h1, ull h2, ll h2len) const {
        ull ret = mul(h1, power[h2len]) + h2;
        if(ret >= mod) ret -= mod;
        return ret;
    }
    
    void connect(const string &s){
        ll n = hashed.size() - 1, m = s.size();
        hashed.resize(n + m + 1);
        power.resize(n + m + 1);
        rep(i, n, n + m) {
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = mul(hashed[i], base) + s[i - n];
            if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
        }
    }
    
    ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) {
        ll len = min(r1 - l1, r2 - l2);
        ll low = -1, high = len + 1;
        while(high - low > 1) {
            ll mid = (low + high) / 2;
            if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};
signed main(){
    STR(s);
    string t={s[0]};
    ll n=s.size();
    rep(i,1,n){
        t+='$';
        t+=s[i];
    }
    auto mn=manacher(t);
    ll ans=0;
    RollingHash rh(s);
    vector<pll>a;
    unordered_map<ull,ll>cnt;
    rep(t.size())a.push_back({(i-mn[i]+2)/2,(i+mn[i]+1)/2});
    auto comp=[](pll a,pll b){return a.second-a.first<b.second-b.first;};
    priority_queue<pll,vector<pll>,decltype(comp)>q(comp);
    unordered_set<ull>used;
    each(i,a){
        q.push(i);
        cnt[rh.get(i.first,i.second)]++;
    }
    while(q.size()){
        auto [l,r]=q.top();
        q.pop();
        if(l>=r)continue;
        ll hash=rh.get(l,r);
        if(used.count(hash))continue;
        used.insert(hash);
        chmax(ans,cnt[hash]*(r-l));
        if(r-l>2){
            l++;
            r--;
            cnt[rh.get(l,r)]+=cnt[hash];
            q.emplace(l,r);
        }
    }
    out(ans);
}

Compilation message

palindrome.cpp: In function 'std::vector<int> manacher(const string&)':
palindrome.cpp:154:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i < s.size()) {
         ~~^~~~~~~~~~
palindrome.cpp:155:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j]) {
                         ~~~~~~^~~~~~~~~~
palindrome.cpp:160:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i - k >= 0 && i + k < s.size() && k + radius[i - k] < j) {
                         ~~~~~~^~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:25:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep1(n) for(ll i=0;i<n;++i)
                             ^
palindrome.cpp:23:41: note: in expansion of macro 'rep1'
 #define overload4(_1,_2,_3,_4,name,...) name
                                         ^~~~
palindrome.cpp:29:18: note: in expansion of macro 'overload4'
 #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
                  ^~~~~~~~~
palindrome.cpp:252:5: note: in expansion of macro 'rep'
     rep(t.size())a.push_back({(i-mn[i]+2)/2,(i+mn[i]+1)/2});
     ^~~
palindrome.cpp: In function 'void scan(int&)':
palindrome.cpp:81:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(int& a){ scanf("%d", &a); }
                    ~~~~~^~~~~~~~~~
palindrome.cpp: In function 'void scan(unsigned int&)':
palindrome.cpp:82:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(unsigned& a){ scanf("%u", &a); }
                         ~~~~~^~~~~~~~~~
palindrome.cpp: In function 'void scan(long int&)':
palindrome.cpp:83:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(long& a){ scanf("%ld", &a); }
                     ~~~~~^~~~~~~~~~~
palindrome.cpp: In function 'void scan(long long int&)':
palindrome.cpp:84:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(long long& a){ scanf("%lld", &a); }
                          ~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'void scan(long long unsigned int&)':
palindrome.cpp:85:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(unsigned long long& a){ scanf("%llu", &a); }
                                   ~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'void scan(float&)':
palindrome.cpp:87:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(float& a){ scanf("%f", &a); }
                      ~~~~~^~~~~~~~~~
palindrome.cpp: In function 'void scan(double&)':
palindrome.cpp:88:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(double& a){ scanf("%lf", &a); }
                       ~~~~~^~~~~~~~~~~
palindrome.cpp: In function 'void scan(long double&)':
palindrome.cpp:89:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(long double& a){ scanf("%Lf", &a); }
                            ~~~~~^~~~~~~~~~~
palindrome.cpp: In function 'void scan(char*)':
palindrome.cpp:91:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(char a[]){ scanf("%s", a); }
                      ~~~~~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 14 ms 2060 KB Output is correct
2 Correct 14 ms 2060 KB Output is correct
3 Correct 15 ms 2060 KB Output is correct
4 Correct 15 ms 2060 KB Output is correct
5 Correct 13 ms 2076 KB Output is correct
6 Correct 14 ms 2088 KB Output is correct
7 Correct 16 ms 2060 KB Output is correct
8 Correct 9 ms 1676 KB Output is correct
9 Correct 9 ms 1676 KB Output is correct
10 Correct 12 ms 1948 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 147 ms 17448 KB Output is correct
2 Correct 157 ms 17248 KB Output is correct
3 Correct 143 ms 17324 KB Output is correct
4 Correct 153 ms 17248 KB Output is correct
5 Correct 120 ms 17304 KB Output is correct
6 Correct 106 ms 15584 KB Output is correct
7 Correct 135 ms 16352 KB Output is correct
8 Correct 53 ms 12396 KB Output is correct
9 Correct 71 ms 12388 KB Output is correct
10 Correct 113 ms 16408 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 591 ms 53100 KB Output is correct
2 Correct 612 ms 53176 KB Output is correct
3 Correct 649 ms 53152 KB Output is correct
4 Correct 654 ms 53280 KB Output is correct
5 Correct 490 ms 53124 KB Output is correct
6 Correct 555 ms 50968 KB Output is correct
7 Correct 567 ms 50464 KB Output is correct
8 Correct 174 ms 42528 KB Output is correct
9 Correct 172 ms 42680 KB Output is correct
10 Correct 457 ms 51720 KB Output is correct
11 Correct 541 ms 53152 KB Output is correct
12 Correct 199 ms 42532 KB Output is correct