oj.uz

Submission #561462

# Submission time Handle Problem Language Result Execution time Memory
561462 2022-05-12T20:42:42 Z Ooops_sorry Palindromes (APIO14_palindrome) C++17
100 / 100
 79 ms 81156 KB 
#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:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      |

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 80076 KB Output is correct
2 Correct 42 ms 80080 KB Output is correct
3 Correct 43 ms 80076 KB Output is correct
4 Correct 44 ms 80156 KB Output is correct
5 Correct 46 ms 80116 KB Output is correct
6 Correct 57 ms 80068 KB Output is correct
7 Correct 59 ms 80092 KB Output is correct
8 Correct 44 ms 80116 KB Output is correct
9 Correct 42 ms 80152 KB Output is correct
10 Correct 43 ms 80048 KB Output is correct
11 Correct 45 ms 80140 KB Output is correct
12 Correct 43 ms 80128 KB Output is correct
13 Correct 48 ms 80164 KB Output is correct
14 Correct 53 ms 80028 KB Output is correct
15 Correct 43 ms 80076 KB Output is correct
16 Correct 45 ms 80096 KB Output is correct
17 Correct 47 ms 80152 KB Output is correct
18 Correct 44 ms 80104 KB Output is correct
19 Correct 46 ms 80076 KB Output is correct
20 Correct 48 ms 80140 KB Output is correct
21 Correct 43 ms 80144 KB Output is correct
22 Correct 46 ms 80204 KB Output is correct
23 Correct 45 ms 80184 KB Output is correct
24 Correct 42 ms 80076 KB Output is correct
25 Correct 51 ms 80104 KB Output is correct
26 Correct 48 ms 80076 KB Output is correct
27 Correct 59 ms 80048 KB Output is correct
28 Correct 42 ms 80076 KB Output is correct
29 Correct 42 ms 80084 KB Output is correct
30 Correct 46 ms 80140 KB Output is correct
31 Correct 42 ms 80136 KB Output is correct
32 Correct 44 ms 80084 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 80120 KB Output is correct
2 Correct 50 ms 80116 KB Output is correct
3 Correct 44 ms 80216 KB Output is correct
4 Correct 43 ms 80076 KB Output is correct
5 Correct 46 ms 80136 KB Output is correct
6 Correct 46 ms 80156 KB Output is correct
7 Correct 49 ms 80104 KB Output is correct
8 Correct 46 ms 80084 KB Output is correct
9 Correct 45 ms 80128 KB Output is correct
10 Correct 44 ms 80108 KB Output is correct
11 Correct 46 ms 80084 KB Output is correct
12 Correct 45 ms 80160 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 80076 KB Output is correct
2 Correct 46 ms 80076 KB Output is correct
3 Correct 44 ms 80076 KB Output is correct
4 Correct 43 ms 80184 KB Output is correct
5 Correct 54 ms 80168 KB Output is correct
6 Correct 47 ms 80112 KB Output is correct
7 Correct 45 ms 80136 KB Output is correct
8 Correct 46 ms 80124 KB Output is correct
9 Correct 48 ms 80140 KB Output is correct
10 Correct 69 ms 80080 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 80372 KB Output is correct
2 Correct 48 ms 80408 KB Output is correct
3 Correct 48 ms 80424 KB Output is correct
4 Correct 47 ms 80468 KB Output is correct
5 Correct 53 ms 80464 KB Output is correct
6 Correct 53 ms 80412 KB Output is correct
7 Correct 47 ms 80428 KB Output is correct
8 Correct 47 ms 80404 KB Output is correct
9 Correct 48 ms 80420 KB Output is correct
10 Correct 51 ms 80420 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 81088 KB Output is correct
2 Correct 57 ms 81100 KB Output is correct
3 Correct 54 ms 81156 KB Output is correct
4 Correct 56 ms 81104 KB Output is correct
5 Correct 69 ms 81072 KB Output is correct
6 Correct 65 ms 81108 KB Output is correct
7 Correct 63 ms 81152 KB Output is correct
8 Correct 49 ms 81108 KB Output is correct
9 Correct 50 ms 81060 KB Output is correct
10 Correct 66 ms 81128 KB Output is correct
11 Correct 79 ms 81108 KB Output is correct
12 Correct 50 ms 81108 KB Output is correct