oj.uz

Submission #47996

# Submission time Handle Problem Language Result Execution time Memory
47996 2018-05-09T10:50:07 Z Kmcode Palindromes (APIO14_palindrome) C++14
100 / 100
 39 ms 35796 KB 
#include "bits/stdc++.h"
using namespace std;

#define MAX 300015
char buf[MAX];string s;int len[MAX];int linkk[MAX];int nex[MAX][26];int ord;int cur;int cnt[MAX];void append(int idx) {char c = s[idx];while (!(idx-len[cur]-1>=0&&s[idx]==s[idx-len[cur]-1])) {cur = linkk[cur];}if (nex[cur][c - 'a'] == -1) {nex[cur][c - 'a'] = ord;ord++;len[nex[cur][c - 'a']] = len[cur] + 2;linkk[nex[cur][c - 'a']] = linkk[cur];cur = nex[cur][c - 'a'];
if (len[cur] == 1) {linkk[cur] = 1;}		else {
			while (!(idx-len[linkk[cur]]-1>=0&&s[idx]==s[idx-len[linkk[cur]]-1])) {linkk[cur] = linkk[linkk[cur]];
			}linkk[cur] = nex[linkk[cur]][c - 'a'];if (linkk[cur] <= 1)exit(1);}}else {cur = nex[cur][c - 'a'];}cnt[cur]++;}int main() {memset(nex, -1,sizeof(nex) );len[0] = -1;len[1] = 0;ord = 2;scanf("%s", buf);s = buf;linkk[1] = 0;linkk[0] = -1;for (int i = 0; i < s.size(); i++) {append(i);	}long long int ans = 0;for (int i = ord - 1; i >= 2; i--) {cnt[linkk[i]] += cnt[i];ans = max(ans, (long long int)(len[i])*cnt[i]);
	}printf("%lld\n", ans);return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:8:258: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    }linkk[cur] = nex[linkk[cur]][c - 'a'];if (linkk[cur] <= 1)exit(1);}}else {cur = nex[cur][c - 'a'];}cnt[cur]++;}int main() {memset(nex, -1,sizeof(nex) );len[0] = -1;len[1] = 0;ord = 2;scanf("%s", buf);s = buf;linkk[1] = 0;linkk[0] = -1;for (int i = 0; i < s.size(); i++) {append(i); }long long int ans = 0;for (int i = ord - 1; i >= 2; i--) {cnt[linkk[i]] += cnt[i];ans = max(ans, (long long int)(len[i])*cnt[i]);
                                                                                                                                                                                                                                                                ~~^~~~~~~~~~
palindrome.cpp:8:193: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    }linkk[cur] = nex[linkk[cur]][c - 'a'];if (linkk[cur] <= 1)exit(1);}}else {cur = nex[cur][c - 'a'];}cnt[cur]++;}int main() {memset(nex, -1,sizeof(nex) );len[0] = -1;len[1] = 0;ord = 2;scanf("%s", buf);s = buf;linkk[1] = 0;linkk[0] = -1;for (int i = 0; i < s.size(); i++) {append(i); }long long int ans = 0;for (int i = ord - 1; i >= 2; i--) {cnt[linkk[i]] += cnt[i];ans = max(ans, (long long int)(len[i])*cnt[i]);
                                                                                                                                                                                            ~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 30840 KB Output is correct
2 Correct 24 ms 30840 KB Output is correct
3 Correct 24 ms 30984 KB Output is correct
4 Correct 24 ms 31060 KB Output is correct
5 Correct 24 ms 31136 KB Output is correct
6 Correct 24 ms 31152 KB Output is correct
7 Correct 24 ms 31152 KB Output is correct
8 Correct 25 ms 31152 KB Output is correct
9 Correct 25 ms 31152 KB Output is correct
10 Correct 25 ms 31152 KB Output is correct
11 Correct 24 ms 31164 KB Output is correct
12 Correct 24 ms 31164 KB Output is correct
13 Correct 24 ms 31164 KB Output is correct
14 Correct 23 ms 31164 KB Output is correct
15 Correct 25 ms 31164 KB Output is correct
16 Correct 24 ms 31164 KB Output is correct
17 Correct 24 ms 31164 KB Output is correct
18 Correct 25 ms 31164 KB Output is correct
19 Correct 25 ms 31180 KB Output is correct
20 Correct 24 ms 31180 KB Output is correct
21 Correct 24 ms 31200 KB Output is correct
22 Correct 24 ms 31200 KB Output is correct
23 Correct 24 ms 31200 KB Output is correct
24 Correct 25 ms 31200 KB Output is correct
25 Correct 24 ms 31200 KB Output is correct
26 Correct 26 ms 31200 KB Output is correct
27 Correct 24 ms 31212 KB Output is correct
28 Correct 24 ms 31216 KB Output is correct
29 Correct 24 ms 31216 KB Output is correct
30 Correct 24 ms 31216 KB Output is correct
31 Correct 32 ms 31216 KB Output is correct
32 Correct 25 ms 31236 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31316 KB Output is correct
2 Correct 24 ms 31316 KB Output is correct
3 Correct 24 ms 31316 KB Output is correct
4 Correct 25 ms 31444 KB Output is correct
5 Correct 25 ms 31444 KB Output is correct
6 Correct 24 ms 31444 KB Output is correct
7 Correct 24 ms 31444 KB Output is correct
8 Correct 24 ms 31444 KB Output is correct
9 Correct 26 ms 31444 KB Output is correct
10 Correct 24 ms 31444 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32596 KB Output is correct
2 Correct 27 ms 32596 KB Output is correct
3 Correct 27 ms 32596 KB Output is correct
4 Correct 27 ms 32596 KB Output is correct
5 Correct 29 ms 32596 KB Output is correct
6 Correct 31 ms 32596 KB Output is correct
7 Correct 28 ms 32596 KB Output is correct
8 Correct 26 ms 32596 KB Output is correct
9 Correct 27 ms 32596 KB Output is correct
10 Correct 28 ms 32596 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35284 KB Output is correct
2 Correct 34 ms 35284 KB Output is correct
3 Correct 34 ms 35284 KB Output is correct
4 Correct 37 ms 35284 KB Output is correct
5 Correct 36 ms 35284 KB Output is correct
6 Correct 39 ms 35284 KB Output is correct
7 Correct 35 ms 35284 KB Output is correct
8 Correct 30 ms 35284 KB Output is correct
9 Correct 29 ms 35284 KB Output is correct
10 Correct 35 ms 35284 KB Output is correct
11 Correct 36 ms 35796 KB Output is correct
12 Correct 31 ms 35796 KB Output is correct