Submission #234848

#	Time	Username	Problem	Language	Result	Execution time	Memory
234848		jhnah917	Palindromes (APIO14_palindrome)	C++14	Compilation error	0 ms	0 KiB

palindrome

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const ll p1 = 179, mod1 = 1e9-63;
const ll p2 = 917, mod2 = 1e9+7;

struct pair_hash{
  template <typename T1, typanameT2>
  size_t operator () (const pair<T1, T2> &t) const {
    return std::hash<T1>()(t.first) ^ std::hash<T2>()(t.second);
  }
};
 
int n;
char s[606060];
int dp[606060];
ll ha1[303030], pw1[303030];
ll ha2[303030], pw2[303030];
 
int pv = 0;
unordered_map<pair<ll, ll>, int, pair_hash> mp;
int cnt[303030];
int len[303030];
int lnk[303030];
vector<int> g[303030];
 
void manacher(){
    for(int i=n-1; i>=0; i--){
        s[i << 1 | 1] = s[i];
        s[i << 1] = '#';
    }
    n <<= 1; s[n++] = '#';
    int r = -1, p = -1;
    for(int i=0; i<n; i++){
        dp[i] = (i <= r ? min(dp[p*2-i], r-i) : 0);
        while(i-dp[i]-1 >= 0 && i+dp[i]+1 < n && s[i-dp[i]-1] == s[i+dp[i]+1]) dp[i]++;
        if(i+dp[i] > r) r = i+dp[i], p = i;
    }
}
pair<ll, ll> substr(int l, int r){
    ll r1 = ha1[l] - ha1[r+1] * pw1[r-l+1]; r1 %= mod1; if(r1 < 0) r1 += mod1;
    ll r2 = ha2[l] - ha2[r+1] * pw2[r-l+1]; r2 %= mod2; if(r2 < 0) r2 += mod2;
    return {r1, r2};
}
 
void go(int s, int e, pair<ll, ll> now){
    if(e-s+1 <= 2) return;
    auto par = substr(s+1, e-1);
    int v = mp[now], u;
    if(!mp.count(par)){
        u = mp[par] = ++pv; len[u] = e-s-1;
    }else u = mp[par];
    if(lnk[v]) return; lnk[v] = 1;
    g[u].push_back(v);
    go(s+1, e-1, par);
}
 
int sz[303030];
int chk[303030];
void dfs(int v){
    sz[v] = cnt[v];
    chk[v] = 1;
    for(auto i : g[v]){
        if(chk[i]) continue;
        dfs(i); sz[v] += sz[i];
    }
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> s; n = strlen(s);
    pw1[0] = 1, pw1[1] = p1;
    pw2[0] = 1, pw2[1] = p2;
    for(int i=n-1; i>=0; i--) ha1[i] = (ha1[i+1] * p1 + s[i]) % mod1;
    for(int i=2; i<=n; i++) pw1[i] = pw1[i-1] * p1 % mod1;
    for(int i=n-1; i>=0; i--) ha2[i] = (ha2[i+1] * p2 + s[i]) % mod2;
    for(int i=2; i<=n; i++) pw2[i] = pw2[i-1] * p2 % mod2;
    manacher();
 
    //for(int i=0; i<n; i++) cout << s[i] << " "; cout << "\n";
    //for(int i=0; i<n; i++) cout << dp[i] << " "; cout << "\n";
 
    for(int i=0; i<n; i++){
        if(!dp[i]) continue;
        int s, e;
        if(i & 1) s = i/2-dp[i]/2, e = i/2+dp[i]/2;
        else{
            s = i-1, e = i+1; s /= 2, e /= 2;
            s -= dp[i]/2-1;
            e += dp[i]/2-1;
        }
        auto now = substr(s, e);
        if(!mp.count(now)){
            mp[now] = ++pv; len[mp[now]] = e-s+1;
        }
        cnt[mp[now]]++;
        go(s, e, now);
    }
 
    ll ans = 0;
    for(int i=1; i<=pv; i++) if(!sz[i]) dfs(i);
    for(int i=1; i<=pv; i++){
        ans = max(ans, (ll)len[i] * sz[i]);
    }
    cout << ans;
};
 
// banana

Compilation message (stderr)

palindrome.cpp:11:26: error: 'typanameT2' has not been declared
   template <typename T1, typanameT2>
                          ^~~~~~~~~~
palindrome.cpp:12:38: error: 'T2' was not declared in this scope
   size_t operator () (const pair<T1, T2> &t) const {
                                      ^~
palindrome.cpp:12:38: note: suggested alternative: 'p2'
   size_t operator () (const pair<T1, T2> &t) const {
                                      ^~
                                      p2
palindrome.cpp:12:40: error: template argument 2 is invalid
   size_t operator () (const pair<T1, T2> &t) const {
                                        ^
palindrome.cpp: In member function 'size_t pair_hash::operator()(const int&) const':
palindrome.cpp:13:30: error: request for member 'first' in 't', which is of non-class type 'const int'
     return std::hash<T1>()(t.first) ^ std::hash<T2>()(t.second);
                              ^~~~~
palindrome.cpp:13:49: error: 'T2' was not declared in this scope
     return std::hash<T1>()(t.first) ^ std::hash<T2>()(t.second);
                                                 ^~
palindrome.cpp:13:49: note: suggested alternative: 'T1'
     return std::hash<T1>()(t.first) ^ std::hash<T2>()(t.second);
                                                 ^~
                                                 T1
palindrome.cpp:13:51: error: template argument 1 is invalid
     return std::hash<T1>()(t.first) ^ std::hash<T2>()(t.second);
                                                   ^
palindrome.cpp:13:57: error: request for member 'second' in 't', which is of non-class type 'const int'
     return std::hash<T1>()(t.first) ^ std::hash<T2>()(t.second);
                                                         ^~~~~~
In file included from /usr/include/c++/7/bits/hashtable.h:35:0,
                 from /usr/include/c++/7/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from palindrome.cpp:3:
/usr/include/c++/7/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash>':
/usr/include/c++/7/type_traits:143:12:   required from 'struct std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> >'
/usr/include/c++/7/type_traits:154:31:   required from 'struct std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>'
palindrome.cpp:24:45:   required from here
/usr/include/c++/7/bits/hashtable_policy.h:87:34: error: no match for call to '(const pair_hash) (const std::pair<long long int, long long int>&)'
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:12:10: note: candidate: template<class T1, <typeprefixerror><anonymous> > size_t pair_hash::operator()(const int&) const
   size_t operator () (const pair<T1, T2> &t) const {
          ^~~~~~~~
palindrome.cpp:12:10: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/hashtable.h:35:0,
                 from /usr/include/c++/7/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from palindrome.cpp:3:
/usr/include/c++/7/bits/hashtable_policy.h:87:34: note:   couldn't deduce template parameter 'T1'
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from palindrome.cpp:3:
/usr/include/c++/7/type_traits: In instantiation of 'struct std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >':
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>'
palindrome.cpp:24:45:   required from here
/usr/include/c++/7/type_traits:154:31: error: 'value' is not a member of 'std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> >'
     : public __bool_constant<!bool(_Pp::value)>
                               ^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/unordered_map:48:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from palindrome.cpp:3:
/usr/include/c++/7/bits/unordered_map.h: In instantiation of 'class std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>':
palindrome.cpp:24:45:   required from here
/usr/include/c++/7/bits/unordered_map.h:103:66: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
                                                                  ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:110:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::key_type key_type;
                                             ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:111:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::value_type value_type;
                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:112:48: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::mapped_type mapped_type;
                                                ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:113:43: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::hasher hasher;
                                           ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:114:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::key_equal key_equal;
                                              ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:115:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::allocator_type allocator_type;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:120:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::pointer  pointer;
                                             ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:121:50: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::const_pointer const_pointer;
                                                  ^~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:122:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::reference  reference;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:123:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::const_reference const_reference;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:124:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::iterator  iterator;
                                              ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:125:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::const_iterator const_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:126:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::local_iterator local_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:127:57: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::const_local_iterator const_local_iterator;
                                                         ^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:128:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::size_type  size_type;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:129:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       typedef typename _Hashtable::difference_type difference_type;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:288:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       operator=(initializer_list<value_type> __l)
       ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:386:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
  emplace(_Args&&... __args)
  ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:578:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       insert(const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:584:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       insert(value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:591:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
  insert(_Pair&& __x)
  ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:657:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       insert(initializer_list<value_type> __l)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:953:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       equal_range(const key_type& __x)
       ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:957:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<pair_hash>, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, pair_hash> > >'
       equal_range(const key_type& __x) const
       ^~~~~~~~~~~
palindrome.cpp: In function 'void go(int, int, std::pair<long long int, long long int>)':
palindrome.cpp:52:15: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' and 'std::pair<long long int, long long int>')
     int v = mp[now], u;
               ^
palindrome.cpp:53:12: error: 'class std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' has no member named 'count'
     if(!mp.count(par)){
            ^~~~~
palindrome.cpp:54:9: error: 'u' was not declared in this scope
         u = mp[par] = ++pv; len[u] = e-s-1;
         ^
palindrome.cpp:54:15: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' and 'std::pair<long long int, long long int>')
         u = mp[par] = ++pv; len[u] = e-s-1;
               ^
palindrome.cpp:55:11: error: 'u' was not declared in this scope
     }else u = mp[par];
           ^
palindrome.cpp:55:17: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' and 'std::pair<long long int, long long int>')
     }else u = mp[par];
                 ^
palindrome.cpp:56:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(lnk[v]) return; lnk[v] = 1;
     ^~
palindrome.cpp:56:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if(lnk[v]) return; lnk[v] = 1;
                        ^~~
palindrome.cpp:57:7: error: 'u' was not declared in this scope
     g[u].push_back(v);
       ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:96:16: error: 'class std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' has no member named 'count'
         if(!mp.count(now)){
                ^~~~~
palindrome.cpp:97:15: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' and 'std::pair<long long int, long long int>')
             mp[now] = ++pv; len[mp[now]] = e-s+1;
               ^
palindrome.cpp:97:35: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' and 'std::pair<long long int, long long int>')
             mp[now] = ++pv; len[mp[now]] = e-s+1;
                                   ^
palindrome.cpp:99:15: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<long long int, long long int>, int, pair_hash>' and 'std::pair<long long int, long long int>')
         cnt[mp[now]]++;
               ^