oj.uz

Submission #42096

# Submission time Handle Problem Language Result Execution time Memory
42096 2018-02-22T13:21:57 Z RockyB Palindromes (APIO14_palindrome) C++14
100 / 100
 525 ms 67236 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 = 217;
 
struct hsh {
	#define hack pair <int, int> 
	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 size_t operator()(const pair<int,int>&x)const{
    return hash<int>() (x.f ^ (x.s << 16));
  }
};

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 18 ms 16760 KB Output is correct
2 Correct 15 ms 16916 KB Output is correct
3 Correct 15 ms 16936 KB Output is correct
4 Correct 15 ms 16936 KB Output is correct
5 Correct 15 ms 17000 KB Output is correct
6 Correct 16 ms 17000 KB Output is correct
7 Correct 15 ms 17000 KB Output is correct
8 Correct 15 ms 17000 KB Output is correct
9 Correct 15 ms 17000 KB Output is correct
10 Correct 15 ms 17004 KB Output is correct
11 Correct 15 ms 17004 KB Output is correct
12 Correct 14 ms 17048 KB Output is correct
13 Correct 15 ms 17048 KB Output is correct
14 Correct 15 ms 17048 KB Output is correct
15 Correct 16 ms 17048 KB Output is correct
16 Correct 15 ms 17048 KB Output is correct
17 Correct 16 ms 17048 KB Output is correct
18 Correct 17 ms 17048 KB Output is correct
19 Correct 16 ms 17048 KB Output is correct
20 Correct 15 ms 17048 KB Output is correct
21 Correct 14 ms 17048 KB Output is correct
22 Correct 15 ms 17048 KB Output is correct
23 Correct 15 ms 17048 KB Output is correct
24 Correct 15 ms 17048 KB Output is correct
25 Correct 18 ms 17048 KB Output is correct
26 Correct 15 ms 17048 KB Output is correct
27 Correct 15 ms 17172 KB Output is correct
28 Correct 15 ms 17172 KB Output is correct
29 Correct 16 ms 17172 KB Output is correct
30 Correct 15 ms 17172 KB Output is correct
31 Correct 15 ms 17172 KB Output is correct
32 Correct 15 ms 17172 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17176 KB Output is correct
2 Correct 16 ms 17176 KB Output is correct
3 Correct 16 ms 17176 KB Output is correct
4 Correct 16 ms 17212 KB Output is correct
5 Correct 15 ms 17212 KB Output is correct
6 Correct 16 ms 17212 KB Output is correct
7 Correct 16 ms 17212 KB Output is correct
8 Correct 15 ms 17212 KB Output is correct
9 Correct 15 ms 17212 KB Output is correct
10 Correct 16 ms 17212 KB Output is correct
11 Correct 17 ms 17212 KB Output is correct
12 Correct 16 ms 17212 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 18672 KB Output is correct
2 Correct 23 ms 18672 KB Output is correct
3 Correct 24 ms 18672 KB Output is correct
4 Correct 26 ms 18796 KB Output is correct
5 Correct 21 ms 18796 KB Output is correct
6 Correct 23 ms 18796 KB Output is correct
7 Correct 24 ms 18796 KB Output is correct
8 Correct 20 ms 18796 KB Output is correct
9 Correct 20 ms 18796 KB Output is correct
10 Correct 22 ms 18796 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 33644 KB Output is correct
2 Correct 141 ms 33644 KB Output is correct
3 Correct 161 ms 33728 KB Output is correct
4 Correct 139 ms 33728 KB Output is correct
5 Correct 114 ms 33728 KB Output is correct
6 Correct 111 ms 33728 KB Output is correct
7 Correct 117 ms 33728 KB Output is correct
8 Correct 71 ms 33728 KB Output is correct
9 Correct 88 ms 33728 KB Output is correct
10 Correct 105 ms 33728 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 66888 KB Output is correct
2 Correct 441 ms 66888 KB Output is correct
3 Correct 525 ms 67236 KB Output is correct
4 Correct 483 ms 67236 KB Output is correct
5 Correct 351 ms 67236 KB Output is correct
6 Correct 445 ms 67236 KB Output is correct
7 Correct 448 ms 67236 KB Output is correct
8 Correct 243 ms 67236 KB Output is correct
9 Correct 226 ms 67236 KB Output is correct
10 Correct 374 ms 67236 KB Output is correct
11 Correct 437 ms 67236 KB Output is correct
12 Correct 238 ms 67236 KB Output is correct