oj.uz

Submission #240679

# Submission time Handle Problem Language Result Execution time Memory
240679 2020-06-20T16:46:17 Z rqi Palindromes (APIO14_palindrome) C++14
73 / 100
 1000 ms 88492 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
int fstTrue(function<bool(int)> f, int lo, int hi) {
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        int mid = (lo+hi)/2; 
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
    str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}



/**
 * Description: Polynomial hash for substrings with two bases.
 * Source:
    * KACTL
    * https://codeforces.com/contest/1207/submission/59309672
 * Verification: 
    * USACO Dec 17 Plat 1 (LCP :o)
    * CF Check Transcription
 */

typedef array<int,2> H; // bases not too close to ends 
uniform_int_distribution<int> BDIST(0.1*MOD,0.9*MOD);
const H base = {BDIST(rng),BDIST(rng)};
/// const T ibase = {(int)inv(mi(base[0])),(int)inv(mi(base[1]))};
H operator+(H l, H r) { 
    F0R(i,2) if ((l[i] += r[i]) >= MOD) l[i] -= MOD;
    return l; }
H operator-(H l, H r) { 
    F0R(i,2) if ((l[i] -= r[i]) < 0) l[i] += MOD;
    return l; }
H operator*(H l, H r) { 
    F0R(i,2) l[i] = (ll)l[i]*r[i]%MOD;
    return l; }
H makeH(char c) { return {c,c}; }
/// H& operator+=(H& l, H r) { return l = l+r; }
/// H& operator-=(H& l, H r) { return l = l-r; }
/// H& operator*=(H& l, H r) { return l = l*r; }

vector<H> pows = {{1,1}};
struct HashRange {
    str S; vector<H> cum = {{0,0}};
    void add(char c) { S += c; cum.pb(base*cum.bk+makeH(c)); }
    void add(str s) { trav(c,s) add(c); }
    void extend(int len) { while (sz(pows) <= len) pows.pb(base*pows.bk); }
    H hash(int l, int r) { int len = r+1-l; extend(len);
        return cum[r+1]-pows[len]*cum[l]; }
    /**int lcp(HashRange& b) { return first_true([&](int x) { 
        return cum[x] != b.cum[x]; },0,min(sz(S),sz(b.S)))-1; }*/
};

/**
 * Description: insert int, query max xor with some int in the trie
 * Time: O(MXBIT)
 * Source: CF Algorithms Gym
 * Verification: January Easy 2018 - Shubham and Subarray Xor
 */

template<int MX> struct Trie {
    map<H, int> m; //substring --> node
    int nex[MX][26], sz[MX], num = 0; // num is last node in trie

    Trie() { memset(nex,0,sizeof nex); memset(sz,0,sizeof sz); }

    ll traverse(int node, int depth, int mode){ //mode 1 --> odd, mode 2 --> even
        ll curans = 0;
        for(int i = 0; i < 26; i++){
            if(nex[node][i] == 0) continue;
            ckmax(curans, traverse(nex[node][i], depth+1, mode));
            sz[node]+=sz[nex[node][i]];
        }
        int adjust = mode-2;
        ckmax(curans, ll(sz[node])*(depth*2+adjust));
        return curans;
    }

};




int N;
string A;
HashRange h1;
HashRange h2;
Trie<300010> t1;
Trie<300010> t2;
ll ans = 0;

int main() {
    setIO();
    cin >> A;
    N = sz(A);
    h1.add(A);
    reverse(all(A));
    h2.add(A);
    reverse(all(A));
    //dbg(A);
    //Odd length palindromes
    for(int i = 0; i < N; i++){
        int lo = 0;
        int hi = min(i-0, N-1-i);
        while(lo < hi){
            int mid = (lo+hi)/2+1;

            if(h1.hash(i, i+mid) == h2.hash(N-1-i, N-1-(i-mid))){
                lo = mid;
            }
            else hi = mid-1;
        }

        int node = 0;
        int ind = i;
        int maxind = ind+lo;
        if(t1.nex[0][A[i]-'a'] != 0){
            int lo2 = 0;
            int hi2 = lo;
            while(lo2 < hi2){
                int mid2 = (lo2+hi2)/2+1;
                if(t1.m.count(h1.hash(i, i+mid2))){
                    lo2 = mid2;
                }
                else hi2 = mid2-1;
            }
            node = t1.m[h1.hash(i, i+lo2)];
            ind = i+lo2+1;
        }

        for(int j = ind; j <= maxind; j++){
            t1.nex[node][A[j]-'a'] = ++t1.num;
            node = t1.num;
            t1.m[h1.hash(i, j)] = t1.num;
        }

        t1.sz[node]++;
    }

    ckmax(ans, t1.traverse(0, 0, 1));

    //Even length palindromes
    for(int i = 0; i+1 < N; i++){ //middle right after i
        if(A[i] != A[i+1]) continue;
        int lo = 0;
        int hi = min(i-0, N-1-(i+1));

        while(lo < hi){
            int mid = (lo+hi)/2+1;
            if(h1.hash(i+1, i+1+mid) == h2.hash(N-1-i, N-1-(i-mid))){
                lo = mid;
            }
            else hi = mid-1;
        }

        int node = 0;
        int ind = i+1;
        int maxind = ind+lo;
        if(t2.nex[0][A[i+1]-'a'] != 0){
            int lo2 = 0;
            int hi2 = lo;
            while(lo2 < hi2){
                int mid2 = (lo2+hi2)/2+1;
                if(t2.m.count(h1.hash(i+1, i+1+mid2))){
                    lo2 = mid2;
                }
                else hi2 = mid2-1;
            }
            node = t2.m[h1.hash(i+1, i+1+lo2)];
            ind = i+1+lo2+1;
        }

        //dbg(i, node, ind, maxind);

        for(int j = ind; j <= maxind; j++){
            t2.nex[node][A[j]-'a'] = ++t2.num;
            node = t2.num;
            t2.m[h1.hash(i+1, j)] = t2.num;
        }

        t2.sz[node]++;
    }

    //dbg(t2.sz[1]);
    ckmax(ans, t2.traverse(0, 0, 2));

    ps(ans);

    // you should actually read the stuff at the bottom
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
*/

Compilation message

palindrome.cpp: In function 'void setIn(std::__cxx11::string)':
palindrome.cpp:128:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
palindrome.cpp: In function 'void setOut(std::__cxx11::string)':
palindrome.cpp:129:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63736 KB Output is correct
2 Correct 39 ms 63736 KB Output is correct
3 Correct 37 ms 63736 KB Output is correct
4 Correct 37 ms 63740 KB Output is correct
5 Correct 42 ms 63736 KB Output is correct
6 Correct 41 ms 63744 KB Output is correct
7 Correct 37 ms 63736 KB Output is correct
8 Correct 37 ms 63736 KB Output is correct
9 Correct 36 ms 63736 KB Output is correct
10 Correct 40 ms 63736 KB Output is correct
11 Correct 36 ms 63736 KB Output is correct
12 Correct 36 ms 63740 KB Output is correct
13 Correct 38 ms 63744 KB Output is correct
14 Correct 43 ms 63736 KB Output is correct
15 Correct 36 ms 63744 KB Output is correct
16 Correct 37 ms 63736 KB Output is correct
17 Correct 41 ms 63736 KB Output is correct
18 Correct 37 ms 63744 KB Output is correct
19 Correct 37 ms 63872 KB Output is correct
20 Correct 37 ms 63736 KB Output is correct
21 Correct 37 ms 63744 KB Output is correct
22 Correct 37 ms 63736 KB Output is correct
23 Correct 37 ms 63736 KB Output is correct
24 Correct 37 ms 63736 KB Output is correct
25 Correct 37 ms 63736 KB Output is correct
26 Correct 41 ms 63864 KB Output is correct
27 Correct 37 ms 63736 KB Output is correct
28 Correct 37 ms 63736 KB Output is correct
29 Correct 38 ms 63736 KB Output is correct
30 Correct 37 ms 63736 KB Output is correct
31 Correct 37 ms 63740 KB Output is correct
32 Correct 37 ms 63744 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63864 KB Output is correct
2 Correct 39 ms 63864 KB Output is correct
3 Correct 39 ms 63864 KB Output is correct
4 Correct 39 ms 63824 KB Output is correct
5 Correct 39 ms 63864 KB Output is correct
6 Correct 43 ms 63864 KB Output is correct
7 Correct 43 ms 63864 KB Output is correct
8 Correct 41 ms 63872 KB Output is correct
9 Correct 43 ms 63864 KB Output is correct
10 Correct 38 ms 63744 KB Output is correct
11 Correct 39 ms 63736 KB Output is correct
12 Correct 38 ms 63864 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 64888 KB Output is correct
2 Correct 59 ms 64760 KB Output is correct
3 Correct 77 ms 64888 KB Output is correct
4 Correct 82 ms 64760 KB Output is correct
5 Correct 54 ms 64888 KB Output is correct
6 Correct 49 ms 64760 KB Output is correct
7 Correct 56 ms 64760 KB Output is correct
8 Correct 47 ms 64120 KB Output is correct
9 Correct 47 ms 64120 KB Output is correct
10 Correct 47 ms 64504 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 74768 KB Output is correct
2 Correct 478 ms 73576 KB Output is correct
3 Correct 793 ms 74860 KB Output is correct
4 Correct 712 ms 73836 KB Output is correct
5 Correct 165 ms 73836 KB Output is correct
6 Correct 214 ms 71272 KB Output is correct
7 Correct 401 ms 71660 KB Output is correct
8 Correct 106 ms 66920 KB Output is correct
9 Correct 198 ms 67948 KB Output is correct
10 Correct 182 ms 72812 KB Output is correct

Subtask #5
0 / 27.0

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