oj.uz

Submission #560466

# Submission time Handle Problem Language Result Execution time Memory
560466 2022-05-11T13:32:42 Z hhhhaura Palindromes (APIO14_palindrome) C++14
100 / 100
 79 ms 81568 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	struct node {
		vector<int>ch;
		int suf, num, len;
		node() {
			ch.assign(26, 0);
			suf = 1;
			num = 0;
			len = 0;
		}
	};
	const int P = 300005;
	vector<node> v(P, node());
	string s;
	int ii, suf, n;
	void init_(int _n, string _s) {
		n = _n, s = _s;
		ii = 2, suf = 2;
		v[1].len = -1;
		v[2].len = 0;
	}
	void add(int pos) {
		int cur = suf, val = s[pos] - 'a';
		while(true) {
			if(pos - v[cur].len - 1 >= 0 &&
				s[pos - v[cur].len - 1] == s[pos]) break;
			cur = v[cur].suf;
		}
		if(v[cur].ch[val]) {
			suf = v[cur].ch[val];
			v[suf].num += 1;
			return;
		}
		ii++, suf = ii;
		v[cur].ch[val] = ii;
		v[ii].num = 1;
		v[ii].len = v[cur].len + 2;
		if(v[ii].len == 1) {
			v[ii].suf = 2;
			return;
		}
		cur = v[cur].suf;
		while(true) {
			if(pos - v[cur].len - 1 >= 0 &&
				s[pos - v[cur].len - 1] == s[pos]) break;
			cur = v[cur].suf;
		}
		v[ii].suf = v[cur].ch[val];
		return;
	}
	void solve() {
		rep(i, 0, n - 1) add(i);
		rrep(i, 1, ii) {
			int val = v[i].num;
			v[v[i].suf].num += val;
		}
		int ans = 0;
		rep(i, 3, ii) ans = max(ans, v[i].num * v[i].len);
		cout << ans << "\n";
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	string s; cin >> s;
	init_(s.size(), s);
	solve();
	return 0;
}

Compilation message

palindrome.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
palindrome.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
palindrome.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 80072 KB Output is correct
2 Correct 44 ms 80128 KB Output is correct
3 Correct 45 ms 80104 KB Output is correct
4 Correct 55 ms 80136 KB Output is correct
5 Correct 47 ms 80068 KB Output is correct
6 Correct 44 ms 80088 KB Output is correct
7 Correct 45 ms 80108 KB Output is correct
8 Correct 44 ms 80076 KB Output is correct
9 Correct 51 ms 80076 KB Output is correct
10 Correct 56 ms 80116 KB Output is correct
11 Correct 46 ms 80044 KB Output is correct
12 Correct 46 ms 80072 KB Output is correct
13 Correct 44 ms 80092 KB Output is correct
14 Correct 44 ms 80088 KB Output is correct
15 Correct 44 ms 80044 KB Output is correct
16 Correct 44 ms 80128 KB Output is correct
17 Correct 47 ms 80152 KB Output is correct
18 Correct 47 ms 80028 KB Output is correct
19 Correct 47 ms 80152 KB Output is correct
20 Correct 57 ms 80160 KB Output is correct
21 Correct 44 ms 80116 KB Output is correct
22 Correct 44 ms 80072 KB Output is correct
23 Correct 44 ms 80036 KB Output is correct
24 Correct 45 ms 80100 KB Output is correct
25 Correct 57 ms 80120 KB Output is correct
26 Correct 46 ms 80032 KB Output is correct
27 Correct 44 ms 80100 KB Output is correct
28 Correct 43 ms 80076 KB Output is correct
29 Correct 44 ms 80164 KB Output is correct
30 Correct 44 ms 80072 KB Output is correct
31 Correct 46 ms 80112 KB Output is correct
32 Correct 46 ms 80068 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 80128 KB Output is correct
2 Correct 47 ms 80096 KB Output is correct
3 Correct 47 ms 80128 KB Output is correct
4 Correct 47 ms 80156 KB Output is correct
5 Correct 44 ms 80076 KB Output is correct
6 Correct 44 ms 80148 KB Output is correct
7 Correct 46 ms 80152 KB Output is correct
8 Correct 46 ms 80092 KB Output is correct
9 Correct 49 ms 80232 KB Output is correct
10 Correct 47 ms 80044 KB Output is correct
11 Correct 46 ms 80084 KB Output is correct
12 Correct 46 ms 80128 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 80116 KB Output is correct
2 Correct 44 ms 80108 KB Output is correct
3 Correct 44 ms 80172 KB Output is correct
4 Correct 58 ms 80172 KB Output is correct
5 Correct 56 ms 80164 KB Output is correct
6 Correct 48 ms 80148 KB Output is correct
7 Correct 44 ms 80188 KB Output is correct
8 Correct 45 ms 80212 KB Output is correct
9 Correct 45 ms 80204 KB Output is correct
10 Correct 45 ms 80164 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 80476 KB Output is correct
2 Correct 51 ms 80460 KB Output is correct
3 Correct 51 ms 80560 KB Output is correct
4 Correct 67 ms 80680 KB Output is correct
5 Correct 56 ms 80528 KB Output is correct
6 Correct 51 ms 80532 KB Output is correct
7 Correct 51 ms 80528 KB Output is correct
8 Correct 47 ms 80508 KB Output is correct
9 Correct 60 ms 80460 KB Output is correct
10 Correct 55 ms 80460 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 81460 KB Output is correct
2 Correct 64 ms 81412 KB Output is correct
3 Correct 56 ms 81460 KB Output is correct
4 Correct 68 ms 81440 KB Output is correct
5 Correct 79 ms 81468 KB Output is correct
6 Correct 62 ms 81464 KB Output is correct
7 Correct 56 ms 81492 KB Output is correct
8 Correct 49 ms 81364 KB Output is correct
9 Correct 52 ms 81364 KB Output is correct
10 Correct 64 ms 81568 KB Output is correct
11 Correct 58 ms 81440 KB Output is correct
12 Correct 52 ms 81364 KB Output is correct