Submission #561462

#	Time	Username	Problem	Language	Result	Execution time	Memory
561462		Ooops_sorry	Palindromes (APIO14_palindrome)	C++17	100 / 100	79 ms	81156 KiB

palindrome

#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 (stderr)

palindrome.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      |

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27