oj.uz

Submission #91512

# Submission time Handle Problem Language Result Execution time Memory
91512 2018-12-28T02:16:28 Z RezwanArefin01 Palindromes (APIO14_palindrome) C++17
100 / 100
 53 ms 34940 KB 
///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 3e5 + 10; 

int t[N][26], len[N], link[N], occ[N], idx, suff; 
char s[N]; int n; 

bool extend(int pos) {
    int cur = suff, c = s[pos] - 'a';
    int cnt = 0; 
    while(pos - len[cur] - 1 < 0 || s[pos - len[cur] - 1] != s[pos]) 
        cur = link[cur]; 
    if(t[cur][c]) {
        suff = t[cur][c]; 
        ++occ[t[cur][c]];
        return 0; 
    }
    suff = ++idx; 
    t[cur][c] = idx; 
    len[idx] = len[cur] + 2;    
    occ[idx] = 1; 
    if(len[idx] == 1) {
        link[idx] = 2; 
        return 1;
    }
    cur = link[cur];
    while(pos - len[cur] - 1 < 0 || s[pos - len[cur] - 1] != s[pos]) 
        cur = link[cur]; 
    link[idx] = t[cur][c]; 
    return 1; 
}

void init() {
    len[1] = -1, link[1] = 1; 
    len[2] = 0, link[2] = 1; 
    idx = suff = 2; 
}

int main(int argc, char const *argv[]) {
	scanf("%s", s); n = strlen(s); 

    init(); 
    for(int i = 0; i < n; ++i) 
        extend(i); 

    ll ans = 0; 
    for(int i = idx; i >= 3; --i)  {
        occ[link[i]] += occ[i]; 
        ans = max(ans, (ll) len[i] * occ[i]); 
    }
    printf("%lld\n", ans); 
}

Compilation message

palindrome.cpp: In function 'bool extend(int)':
palindrome.cpp:18:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0; 
         ^~~
palindrome.cpp: In function 'int main(int, const char**)':
palindrome.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s); n = strlen(s); 
  ~~~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 2 ms 652 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 652 KB Output is correct
10 Correct 2 ms 652 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 2 ms 652 KB Output is correct
14 Correct 2 ms 652 KB Output is correct
15 Correct 2 ms 652 KB Output is correct
16 Correct 2 ms 652 KB Output is correct
17 Correct 2 ms 652 KB Output is correct
18 Correct 1 ms 652 KB Output is correct
19 Correct 2 ms 652 KB Output is correct
20 Correct 2 ms 652 KB Output is correct
21 Correct 2 ms 652 KB Output is correct
22 Correct 2 ms 652 KB Output is correct
23 Correct 2 ms 652 KB Output is correct
24 Correct 2 ms 652 KB Output is correct
25 Correct 2 ms 652 KB Output is correct
26 Correct 2 ms 652 KB Output is correct
27 Correct 2 ms 652 KB Output is correct
28 Correct 2 ms 652 KB Output is correct
29 Correct 2 ms 652 KB Output is correct
30 Correct 2 ms 652 KB Output is correct
31 Correct 2 ms 652 KB Output is correct
32 Correct 2 ms 652 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 2 ms 764 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 2 ms 764 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1660 KB Output is correct
2 Correct 3 ms 1660 KB Output is correct
3 Correct 3 ms 1788 KB Output is correct
4 Correct 3 ms 1788 KB Output is correct
5 Correct 3 ms 1788 KB Output is correct
6 Correct 3 ms 1788 KB Output is correct
7 Correct 3 ms 1788 KB Output is correct
8 Correct 2 ms 1788 KB Output is correct
9 Correct 2 ms 1788 KB Output is correct
10 Correct 3 ms 1788 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12028 KB Output is correct
2 Correct 15 ms 12028 KB Output is correct
3 Correct 16 ms 12028 KB Output is correct
4 Correct 16 ms 12028 KB Output is correct
5 Correct 16 ms 12028 KB Output is correct
6 Correct 12 ms 12028 KB Output is correct
7 Correct 14 ms 12028 KB Output is correct
8 Correct 3 ms 12028 KB Output is correct
9 Correct 6 ms 12028 KB Output is correct
10 Correct 14 ms 12028 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 34940 KB Output is correct
2 Correct 41 ms 34940 KB Output is correct
3 Correct 43 ms 34940 KB Output is correct
4 Correct 44 ms 34940 KB Output is correct
5 Correct 53 ms 34940 KB Output is correct
6 Correct 37 ms 34940 KB Output is correct
7 Correct 40 ms 34940 KB Output is correct
8 Correct 6 ms 34940 KB Output is correct
9 Correct 6 ms 34940 KB Output is correct
10 Correct 41 ms 34940 KB Output is correct
11 Correct 39 ms 34940 KB Output is correct
12 Correct 9 ms 34940 KB Output is correct