oj.uz

Submission #555030

# Submission time Handle Problem Language Result Execution time Memory
555030 2022-04-30T02:45:34 Z MrDeboo Palindromes (APIO14_palindrome) C++17
23 / 100
 1000 ms 50968 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++){;
        for(int w=i;w<sz(s);w++){
            mp[h.get_hash(i,w)]++;
        }
    }
    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 9 ms 8080 KB Output is correct
2 Correct 10 ms 8052 KB Output is correct
3 Correct 9 ms 8056 KB Output is correct
4 Correct 9 ms 8020 KB Output is correct
5 Correct 9 ms 8020 KB Output is correct
6 Correct 9 ms 8020 KB Output is correct
7 Correct 9 ms 8020 KB Output is correct
8 Correct 9 ms 8020 KB Output is correct
9 Correct 9 ms 8100 KB Output is correct
10 Correct 9 ms 8148 KB Output is correct
11 Correct 9 ms 8148 KB Output is correct
12 Correct 10 ms 8148 KB Output is correct
13 Correct 9 ms 8164 KB Output is correct
14 Correct 9 ms 8148 KB Output is correct
15 Correct 9 ms 8044 KB Output is correct
16 Correct 9 ms 8148 KB Output is correct
17 Correct 9 ms 8148 KB Output is correct
18 Correct 9 ms 8148 KB Output is correct
19 Correct 9 ms 8104 KB Output is correct
20 Correct 9 ms 8052 KB Output is correct
21 Correct 10 ms 8252 KB Output is correct
22 Correct 10 ms 8276 KB Output is correct
23 Correct 9 ms 8148 KB Output is correct
24 Correct 10 ms 8276 KB Output is correct
25 Correct 9 ms 8040 KB Output is correct
26 Correct 10 ms 8276 KB Output is correct
27 Correct 10 ms 8272 KB Output is correct
28 Correct 9 ms 8276 KB Output is correct
29 Correct 10 ms 8316 KB Output is correct
30 Correct 10 ms 8396 KB Output is correct
31 Correct 10 ms 8404 KB Output is correct
32 Correct 10 ms 8336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8224 KB Output is correct
2 Correct 215 ms 24832 KB Output is correct
3 Correct 66 ms 8204 KB Output is correct
4 Correct 353 ms 35880 KB Output is correct
5 Correct 59 ms 8136 KB Output is correct
6 Correct 60 ms 8212 KB Output is correct
7 Correct 297 ms 29260 KB Output is correct
8 Correct 62 ms 8276 KB Output is correct
9 Correct 340 ms 37000 KB Output is correct
10 Correct 340 ms 39020 KB Output is correct
11 Correct 335 ms 39140 KB Output is correct
12 Correct 310 ms 31944 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 9556 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 1099 ms 22368 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 1101 ms 50968 KB Time limit exceeded
2 Halted 0 ms 0 KB -