oj.uz

Submission #42099

# Submission time Handle Problem Language Result Execution time Memory
42099 2018-02-22T13:27:01 Z RockyB Palindromes (APIO14_palindrome) C++14
100 / 100
 639 ms 76524 KB 
/// In The Name Of God
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
 
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
#define nl '\n'
#define ioi exit(0);
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
const int N = (int)3e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
 
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
using namespace std;
 
inline void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}
inline int sum(int x, int y) {
	add(x, y);
	return x;
}
inline int mult(int x, int y) {
	return x * 1ll * y % mod;
}
 
/*struct hashMap {
	static const int Sz = N * 10;
	int h[Sz], t[Sz];
	hashMap() {
		memset(h, 0, sizeof(h));
		memset(t, -1, sizeof(t));
	}
	int add(int x) {
		int mask = (ll)x << 16 % Sz;
		while (t[mask] != -1 && t[mask] != x) mask++;
		t[mask] = x;
		return ++h[mask];
	}
} cnt;*/
 
int n;
int p[N];
char s[N];
 
ll ans;
 
const int p1 = 997;
const int p2 = 2017;
 
struct hsh {
	#define hack pair <int, ull> 
	int len;
	hack h[N], dg[N];
	inline void init(char *x) {
		len = strlen(x + 1);
		dg[0] = {1, 1};
		dg[1] = {p1, p2};
		for (int i = 1; i <= len; i++) {
			h[i + 1].f = sum(mult(h[i].f, p1), x[i]);
			h[i + 1].s = h[i].s * p2 + x[i];
			dg[i + 1].f = mult(dg[i].f, p1);
			dg[i + 1].s = dg[i].s * p2;
		}
	}
	inline hack get(int l, int r) {
		return {sum(h[r + 1].f, -mult(h[l].f, dg[r - l + 1].f)), h[r + 1].s - h[l].s * dg[r - l + 1].s};
	}
} t, t1;
 
inline bool check(int l, int r) {
	return t.get(l, r) == t1.get(n - r + 1, n - l + 1);
}
 
int sz;
int pref[N];
 
vector <int> root;
vector <int> g[N];
 
struct HASH{
  inline ull operator()(const pair<int,ull>&x)const{
    return (x.f ^ (x.s << 32));
  }
};

unordered_map <hack, int, HASH> id;
inline void addOdd(int p, int len) {
	int last = 0;
	for (int i = len; i >= 1; i--) {
		if (id.count(t.get(p - i + 1, p + i - 1))) {
			if (last) g[id[t.get(p - i + 1, p + i - 1)]].pb(last);
			break;
		}	
		id[t.get(p - i + 1, p + i - 1)] = ++sz;
		if (last) g[sz].pb(last);
		last = sz;
		if (i == 1) root.pb(sz);
	}
	pref[id[t.get(p - len + 1, p + len - 1)]]++;
}
inline void addEven(int p, int len) {
	int last = 0;
	for (int i = len; i >= 1; i--) {
		if (id.count(t.get(p - i + 1, p + i))) {
			if (last) g[id[t.get(p - i + 1, p + i)]].pb(last);
			break;
		}	
		id[t.get(p - i + 1, p + i)] = ++sz;
		if (last) g[sz].pb(last);
		last = sz;
		if (i == 1) root.pb(sz);
	}
	pref[id[t.get(p - len + 1, p + len)]]++;
}
 
inline void dfs1(int v, int lvl) {
	for (auto to : g[v]) {
		dfs1(to, lvl + 1);
		pref[v] += pref[to];
	}
	ans = max(ans, (ll)pref[v] * (lvl * 2 - 1));
}
inline void dfs2(int v, int lvl) {
	for (auto to : g[v]) {
		dfs2(to, lvl + 1);
		pref[v] += pref[to];
	}
	ans = max(ans, (ll)pref[v] * lvl * 2);
}
 
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
		//freopen ("slow.out", "w", stdout);
	#endif
	Kazakhstan
	cin >> (s + 1);
	n = strlen(s + 1);
	t.init(s);
	reverse(s + 1, s + 1 + n);
	t1.init(s);
	reverse(s + 1, s + 1 + n);
	/// even
	id.max_load_factor(0.25);
	id.reserve(n << 1);
 
	for (int i = 1; i <= n; i++) {
		int l = 1, r = min(i, n - i), res = 0;
		while (l <= r) {
			int mid = l + r >> 1;
			if (check(i - mid + 1, i + mid)) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		if (res) addEven(i, res);
	}
	for (auto it : root) {
		dfs2(it, 1);
	}
	/// odd
	root.clear();
	for (int i = 1; i <= n; i++) {
		int l = 1, r = min(i, n - i + 1), res = 1;
		while (l <= r) {
			int mid = l + r >> 1;
			if (check(i - mid + 1, i + mid - 1)) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		addOdd(i, res);
	}
	for (auto it : root) {
		dfs1(it, 1);
	}
	cout << ans;
	ioi
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:175:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l + r >> 1;
                ^
palindrome.cpp:189:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l + r >> 1;
                ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26104 KB Output is correct
2 Correct 26 ms 26336 KB Output is correct
3 Correct 22 ms 26336 KB Output is correct
4 Correct 21 ms 26336 KB Output is correct
5 Correct 22 ms 26352 KB Output is correct
6 Correct 21 ms 26352 KB Output is correct
7 Correct 21 ms 26360 KB Output is correct
8 Correct 21 ms 26412 KB Output is correct
9 Correct 21 ms 26412 KB Output is correct
10 Correct 23 ms 26460 KB Output is correct
11 Correct 21 ms 26460 KB Output is correct
12 Correct 23 ms 26460 KB Output is correct
13 Correct 22 ms 26460 KB Output is correct
14 Correct 22 ms 26476 KB Output is correct
15 Correct 22 ms 26476 KB Output is correct
16 Correct 24 ms 26476 KB Output is correct
17 Correct 22 ms 26476 KB Output is correct
18 Correct 21 ms 26476 KB Output is correct
19 Correct 21 ms 26476 KB Output is correct
20 Correct 21 ms 26476 KB Output is correct
21 Correct 21 ms 26476 KB Output is correct
22 Correct 21 ms 26476 KB Output is correct
23 Correct 21 ms 26476 KB Output is correct
24 Correct 22 ms 26476 KB Output is correct
25 Correct 21 ms 26480 KB Output is correct
26 Correct 21 ms 26480 KB Output is correct
27 Correct 21 ms 26572 KB Output is correct
28 Correct 22 ms 26572 KB Output is correct
29 Correct 21 ms 26572 KB Output is correct
30 Correct 21 ms 26572 KB Output is correct
31 Correct 24 ms 26572 KB Output is correct
32 Correct 21 ms 26572 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 28140 KB Output is correct
2 Correct 28 ms 28140 KB Output is correct
3 Correct 41 ms 28140 KB Output is correct
4 Correct 29 ms 28140 KB Output is correct
5 Correct 39 ms 28140 KB Output is correct
6 Correct 28 ms 28140 KB Output is correct
7 Correct 38 ms 28140 KB Output is correct
8 Correct 26 ms 28140 KB Output is correct
9 Correct 25 ms 28140 KB Output is correct
10 Correct 30 ms 28140 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 42988 KB Output is correct
2 Correct 164 ms 42988 KB Output is correct
3 Correct 169 ms 43196 KB Output is correct
4 Correct 192 ms 43196 KB Output is correct
5 Correct 139 ms 43196 KB Output is correct
6 Correct 122 ms 43196 KB Output is correct
7 Correct 146 ms 43196 KB Output is correct
8 Correct 99 ms 43196 KB Output is correct
9 Correct 115 ms 43196 KB Output is correct
10 Correct 119 ms 43196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 76392 KB Output is correct
2 Correct 551 ms 76392 KB Output is correct
3 Correct 626 ms 76524 KB Output is correct
4 Correct 639 ms 76524 KB Output is correct
5 Correct 430 ms 76524 KB Output is correct
6 Correct 459 ms 76524 KB Output is correct
7 Correct 494 ms 76524 KB Output is correct
8 Correct 304 ms 76524 KB Output is correct
9 Correct 301 ms 76524 KB Output is correct
10 Correct 410 ms 76524 KB Output is correct
11 Correct 570 ms 76524 KB Output is correct
12 Correct 322 ms 76524 KB Output is correct