oj.uz

Submission #204742

# Submission time Handle Problem Language Result Execution time Memory
204742 2020-02-26T19:46:24 Z staniewzki Palindromes (APIO14_palindrome) C++17
65 / 100
 1000 ms 10692 KB 
#include<bits/stdc++.h>
using namespace std;
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.first << ", " << p.second << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
template<class T> int size(T && a) { return a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

/*
 * Opis: Tablica suffixowa
 * Status: Cośtam potestowany
 * Czas: O(n \log n)
 * Użycie: SuffixArray t(s, lim) - lim to rozmiar alfabetu
 * sa zawiera posortowane suffixy, zawiera pusty suffix
 * lcp[i] to lcp suffixu sa[i - 1] i sa[i]
 * Dla s = "aabaaab" sa = {6, 3, 0, 4, 1, 5, 2}, lcp = {0, 0, 3, 1, 2, 0, 1}
 */

struct SuffixArray {
	vector<int> sa, lcp, rank;
	SuffixArray(string& s, int lim = 256) { // lub basic_string<int>
		int n = size(s) + 1, k = 0, a, b;
		vector<int> x(s.begin(), s.end() + 1);
		vector<int> y(n), ws(max(n, lim));
		sa = lcp = rank = y;
		iota(sa.begin(), sa.end(), 0);

		for(int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
			p = j;
			iota(y.begin(), y.end(), n - j);
			REP(i, n) if(sa[i] >= j)
				y[p++] = sa[i] - j;
			fill(ws.begin(), ws.end(), 0);
			REP(i, n) ws[x[i]]++;
			FOR(i, 1, lim - 1) ws[i] += ws[i - 1];
			for(int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y);
			p = 1, x[sa[0]] = 0;
			FOR(i, 1, n - 1) a = sa[i - 1], b = sa[i], x[b] =
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		FOR(i, 1, n - 1) rank[sa[i]] = i;
		for(int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for(k && k--, j = sa[rank[i] - 1];
				s[i + k] == s[j + k]; k++);
	}
	int operator[](int x) { return sa[x]; }
};

/*
 * Opis: Drzewo punkt-przedział
 * Czas: O(\log n)
 * Pamięć : O(n)
 * Użycie:
 *   Tree(n, val = 0) tworzy drzewo o n liściach, o wartościach val
 *   update(pos, val) zmienia element pos na val
 *   query(l, r) zwraca f na przedziale
 *   edytujesz funkcję f, można T ustawić na long longa albo parę
 */

struct Tree {
	using T = int;
	T f(T a, T b) { return min(a, b); }
	vector<T> tree;
	int size = 1;

	Tree(int n, T val = 0) {
		while(size < n) size *= 2;
		tree.resize(size * 2, val);
	}

	void update(int pos, T val) {
		tree[pos += size] = val;
		while(pos /= 2)
			tree[pos] = f(tree[pos * 2], tree[pos * 2 + 1]);
	}

	T query(int l, int r) {
		l += size, r += size;
		T ret = (l != r ? f(tree[l], tree[r]) : tree[l]);
		while(l + 1 < r) {
			if(l % 2 == 0)
				ret = f(ret, tree[l + 1]);
			if(r % 2 == 1)
				ret = f(ret, tree[r - 1]);
			l /= 2, r /= 2;
		}
		return ret;
	}
};

/*
 * Opis: radius[p][i] = $rad$ = największy promień palindromu
 *   parzystości p o środku i. $L=i-rad+!p, \; R=i+rad$ to palindrom.
 *   Dla [abaababaab] daje [003000020], [0100141000].
 * Czas: O(n)
 */

array<vector<int>, 2> manacher(string &in) {
	int n = size(in);
	array<vector<int>, 2> radius = {{vector<int>(n - 1), vector<int>(n)}};
	REP(parity, 2) {
		int z = parity ^ 1, L = 0, R = 0;
		REP(i, n - z) {
			int &rad = radius[parity][i];
			if(i <= R - z)
				rad = min(R - i, radius[parity][L + (R - i - z)]);
			int l = i - rad + z, r = i + rad;
			while(0 <= l - 1 && r + 1 < n && in[l - 1] == in[r + 1])
				++rad, ++r, --l;
			if(r > R)
				L = l, R = r;
		}
	}
	return radius;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string str;
	cin >> str;

	int n = size(str);
	SuffixArray sa(str);
	Tree tree(n);
	FOR(i, 1, n - 1)
		tree.update(i, sa.lcp[i]);

	auto get_lcp = [&](int i, int j) {
		if(i == j) return n - i;
		i = sa.rank[i], j = sa.rank[j];
		if(i > j) swap(i, j);
		return tree.query(i + 1, j);
	};

	auto compare = [&](int a, int b, int i, bool equal) {
		int l = get_lcp(a, i);
		if(l >= b - a + 1) return equal;
		if(i + l == n) return false;
		return str[a + l] < str[i + l];
	};

	auto binsearch = [&](int a, int b, bool equal) {
		int l = 1, r = n + 1;
		while(l < r) {
			int mid = (l + r) / 2;
			if(compare(a, b, sa[mid], equal))
				r = mid;
			else
				l = mid + 1;
		}
		return l;
	};

	auto count = [&](int a, int b) -> LL {
		return binsearch(a, b, false) - binsearch(a, b, true);
	};

	auto m = manacher(str);
	LL ans = 0;
	REP(p, 2) REP(i, n + p - 1) {
		int l = i - m[p][i] + 1 - p;
		int r = i + m[p][i];
		if(l <= r) ans = max(ans, count(l, r) * (r - l + 1));
	}

	cout << ans << "\n";
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 424 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 488 KB Output is correct
17 Incorrect 5 ms 380 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 760 KB Output is correct
2 Correct 22 ms 760 KB Output is correct
3 Correct 33 ms 760 KB Output is correct
4 Correct 36 ms 764 KB Output is correct
5 Correct 37 ms 760 KB Output is correct
6 Correct 36 ms 760 KB Output is correct
7 Correct 21 ms 760 KB Output is correct
8 Correct 33 ms 760 KB Output is correct
9 Correct 34 ms 760 KB Output is correct
10 Correct 48 ms 760 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 3620 KB Output is correct
2 Correct 229 ms 3548 KB Output is correct
3 Correct 398 ms 3680 KB Output is correct
4 Correct 447 ms 3680 KB Output is correct
5 Correct 523 ms 3828 KB Output is correct
6 Correct 439 ms 3680 KB Output is correct
7 Correct 418 ms 3740 KB Output is correct
8 Correct 479 ms 3608 KB Output is correct
9 Correct 497 ms 3548 KB Output is correct
10 Correct 674 ms 3676 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 10692 KB Output is correct
2 Correct 809 ms 10692 KB Output is correct
3 Execution timed out 1082 ms 10692 KB Time limit exceeded
4 Halted 0 ms 0 KB -