oj.uz

Submission #555043

# Submission time Handle Problem Language Result Execution time Memory
555043 2022-04-30T03:17:00 Z MrDeboo Palindromes (APIO14_palindrome) C++17
23 / 100
 1000 ms 14064 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<int MOD>
struct ModInt {
    unsigned x;
    ModInt() : x(0) { }
    ModInt(signed sig) : x(sig%MOD) {  }
    ModInt(signed long long sig) : x(sig%MOD) { }
    int get() const { return (int)x; }
    ModInt pow(long long p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }

    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }

    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    bool operator<(ModInt that) const { return x < that.x; }
    friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};

#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define fs first
#define sc second
#define unique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define endl '\n'
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef long double ld;
typedef ModInt<1000000007> mint;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;

const int mxn=200000;
// const ll mod=1000000007;
const ll INF=1000000000000000000;

template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.fs;
	return cin >> p.sc;
}

#define MAXLEN 1000010

constexpr uint64_t mod = (1ULL << 61) - 1;

const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (mod / 3) + (mod / 3);

uint64_t base_pow[MAXLEN];

int64_t modmul(uint64_t a, uint64_t b){
    uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
    uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
    uint64_t ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & mod) + (ret >> 61);
    ret = (ret & mod) + (ret >> 61);
    return ret - 1;
}

void init(){
    base_pow[0] = 1;
    for (int i = 1; i < MAXLEN; i++){
        base_pow[i] = modmul(base_pow[i - 1], base);
    }
}


struct PolyHash{
    /// Remove suff vector and usage if reverse hash is not required for more speed
    vector<int64_t> pref, suff;

    PolyHash() {}

    template <typename T>
    PolyHash(const vector<T>& ar){
        if (!base_pow[0]) init();

        int n = ar.size();
        assert(n < MAXLEN);
        pref.resize(n + 3, 0), suff.resize(n + 3, 0);

        for (int i = 1; i <= n; i++){
            pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
            if (pref[i] >= mod) pref[i] -= mod;
        }

        for (int i = n; i >= 1; i--){
            suff[i] = modmul(suff[i + 1], base) + ar[i - 1] + 997;
            if (suff[i] >= mod) suff[i] -= mod;
        }
    }

    PolyHash(const char* str)
        : PolyHash(vector<char> (str, str + strlen(str))) {}

    uint64_t get_hash(int l, int r){
        int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
        return h < 0 ? h + mod : h;
    }

    uint64_t rev_hash(int l, int r){
        int64_t h = suff[l + 1] - modmul(base_pow[r - l + 1], suff[r + 2]);
        return h < 0 ? h + mod : h;
    }
};

string FileS="";
bool tstc=0;
void dothethingthatfindsthesolutiontotheproblem(){
    string s;
    cin>>s;
    vector<char>c;
    for(auto &i:s)c.push_back(i);
    PolyHash h=PolyHash(c);
    map<ll,ll>mp;
    ll ans=0;
    for(int i=0;i<sz(s);i++){
        int l=i,r=i;
        while(l>=0&&r<sz(s)&&s[l]==s[r]){
            ans=max(ans,++mp[h.get_hash(l,r)]*(r-l+1));
            r++;
            l--;
        }
    }
    for(int i=1;i<sz(s);i++){
        int l=i-1,r=i;
        while(l>=0&&r<sz(s)&&s[l]==s[r]){
            ans=max(ans,++mp[h.get_hash(l,r)]*(r-l+1));
            r++;
            l--;
        }
    }
    cout<<ans;
}


void File(){
    ifstream cin(FileS + ".in");
    ofstream cout(FileS + ".out");
}

int main(){

    send help

    if(FileS.size())File();

    int tc=1;
    if(tstc)cin>>tc;

    while(tc--){
        dothethingthatfindsthesolutiontotheproblem();
    }
}

Compilation message

palindrome.cpp: In instantiation of 'PolyHash::PolyHash(const std::vector<_Tp>&) [with T = char]':
palindrome.cpp:105:57:   required from here
palindrome.cpp:95:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   95 |             if (pref[i] >= mod) pref[i] -= mod;
palindrome.cpp:100:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
  100 |             if (suff[i] >= mod) suff[i] -= mod;

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8052 KB Output is correct
2 Correct 10 ms 8148 KB Output is correct
3 Correct 11 ms 8028 KB Output is correct
4 Correct 10 ms 8020 KB Output is correct
5 Correct 10 ms 8020 KB Output is correct
6 Correct 9 ms 8020 KB Output is correct
7 Correct 11 ms 8052 KB Output is correct
8 Correct 10 ms 8080 KB Output is correct
9 Correct 9 ms 8060 KB Output is correct
10 Correct 10 ms 8100 KB Output is correct
11 Correct 10 ms 8064 KB Output is correct
12 Correct 10 ms 8124 KB Output is correct
13 Correct 9 ms 8020 KB Output is correct
14 Correct 9 ms 8020 KB Output is correct
15 Correct 9 ms 8148 KB Output is correct
16 Correct 9 ms 8148 KB Output is correct
17 Correct 9 ms 8020 KB Output is correct
18 Correct 9 ms 8096 KB Output is correct
19 Correct 9 ms 8148 KB Output is correct
20 Correct 9 ms 8148 KB Output is correct
21 Correct 9 ms 8148 KB Output is correct
22 Correct 9 ms 8104 KB Output is correct
23 Correct 9 ms 8148 KB Output is correct
24 Correct 9 ms 8148 KB Output is correct
25 Correct 9 ms 8088 KB Output is correct
26 Correct 9 ms 8148 KB Output is correct
27 Correct 9 ms 8060 KB Output is correct
28 Correct 9 ms 8148 KB Output is correct
29 Correct 9 ms 8148 KB Output is correct
30 Correct 10 ms 8020 KB Output is correct
31 Correct 9 ms 8148 KB Output is correct
32 Correct 9 ms 8096 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8148 KB Output is correct
2 Correct 15 ms 8232 KB Output is correct
3 Correct 33 ms 8120 KB Output is correct
4 Correct 10 ms 8148 KB Output is correct
5 Correct 33 ms 8244 KB Output is correct
6 Correct 34 ms 8184 KB Output is correct
7 Correct 10 ms 8148 KB Output is correct
8 Correct 25 ms 8228 KB Output is correct
9 Correct 10 ms 8092 KB Output is correct
10 Correct 10 ms 8148 KB Output is correct
11 Correct 9 ms 8148 KB Output is correct
12 Correct 9 ms 8148 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 8872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 10616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 14064 KB Time limit exceeded
2 Halted 0 ms 0 KB -