답안 #42203 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42203	2018-02-23T07:04:27 Z	Aidyn_A	회문 (APIO14_palindrome)	C++14	100 / 100	972 ms	67616 KB

palindrome

#include <stdio.h>
#include <bits/stdc++.h>			
 
#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int N = (int)3e5 + 123;
 
inline int mult(int a, int b, int MOD) {
	return 1ll * a * b % MOD;
}
 
inline int add(int a, int b, int MOD) {
	a += b;
	if(a >= MOD) a -= MOD;
	return a;
}  
 
inline int subs(int a, int b, int MOD) {
	a -= b;
	if(a < 0) a += MOD;
	return a;
}
 
string s;
int h[3][N], P[3], pw[3][N], MOD[3];
int hr[3][N];
   
void build() {
	h[1][0] = h[2][0] = s[0];
	hr[1][0] = hr[2][0] = s[sz(s) - 1];
	for(int it = 1; it <= 2; it ++) {
		for(int i = 1; i < sz(s); i ++) {
			h[it][i] = add(mult(h[it][i - 1], P[it], MOD[it]), s[i], MOD[it]); 
			hr[it][i] = add(mult(hr[it][i - 1], P[it], MOD[it]), s[sz(s) - i - 1], MOD[it]);
		}
	}
}                      
 
inline ll hashPair(pii A) {
	return ((ll)A.F << 16) ^ ((ll)A.S >> 16);
}

inline ll getHash(int l, int r) {
	int A = subs(h[1][r], mult(h[1][l - 1], pw[1][r - l + 1], MOD[1]), MOD[1]);
	int B = subs(h[2][r], mult(h[2][l - 1], pw[2][r - l + 1], MOD[2]), MOD[2]);
	return hashPair(mp(A, B));
}
 
inline ll getHashR(int l, int r) {
	int l1 = sz(s) - r - 1, r1 = sz(s) - l - 1;
	l = l1, r = r1;
	int A = subs(hr[1][r], mult(hr[1][l - 1], pw[1][r - l + 1], MOD[1]), MOD[1]);
	int B = subs(hr[2][r], mult(hr[2][l - 1], pw[2][r - l + 1], MOD[2]), MOD[2]);
	return hashPair(mp(A, B));
}
                             
inline int length(int i, int j) {
	if(s[i] != s[j])
		return 0;
	int l = 0, r = min(i, sz(s) - j) + 1;
	while(r - l > 1) {
		int mid = (l + r) >> 1;
		if(i - mid >= 0 && j + mid < sz(s) && getHash(i - mid, i) == getHashR(j, j + mid))
			l = mid;
		else 	
			r = mid;
	}
	return l;              	
}
 
unordered_map<ll, int> newId;
int vtr;
vector<int> g[N];
int chest[N], dlina[N];
int pr[N];
  
int sub[N];
ll res;
 
void dfs(int x) {
	sub[x] += chest[x];
	for(auto to : g[x]) {
		dfs(to);
		sub[x] += sub[to];
	}
	res = max(res, 1ll * sub[x] * dlina[x]);	
}
 
void calc(bool op) {
	for(int i = op; i < sz(s); i ++) {
		if(s[i - op] != s[i])
			continue;
		int tmp = length(i - op, i), bmp = tmp;
		int prev = -1;
		while(tmp >= 0) {
		  if(!newId.count(getHash(i - tmp - op, i + tmp))) {
		  	newId[getHash(i - tmp - op, i + tmp)] = ++ vtr;
		  	dlina[vtr] = ((tmp + op) << 1) + (op ^ 1);
		  	if(prev != -1) {
		  		g[vtr].pb(prev);
		  		pr[prev] = vtr;
		  	}
		  	prev = vtr;
		  } else { 
		  	if(prev != -1) {
		  		int kepka = newId[getHash(i - tmp - op, i + tmp)]; 
		  		g[kepka].pb(prev);
		  		pr[prev] = kepka;
				}
		  	break;
      }
			tmp --;			
		}
		chest[newId[getHash(i - bmp - op, i + bmp)]] ++;
	}
}
 
int main() {
	P[1] = 997, P[2] = 2017;
	MOD[1] = (int)1e9 + 7, MOD[2] = (int)1e9 + 3;
	for(int it = 1; it <= 2; it ++) {
		pw[it][0] = 1;
		for(int i = 1; i <= N - 123; i ++)
			pw[it][i] = mult(pw[it][i - 1], P[it], MOD[it]); 
	}
	ios_base::sync_with_stdio(0);  cin.tie(0);
	cin >> s;
  newId.max_load_factor(0.25);
  newId.reserve(sz(s) << 1);
	build();
	calc(0); 
	calc(1);
	for(int i = 1; i <= vtr; i ++) { 
 	  if(pr[i]) continue;
		dfs(i);
	}
	cout << res;
	return 0;  
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	9720 KB	Output is correct
2	Correct	12 ms	9824 KB	Output is correct
3	Correct	13 ms	9900 KB	Output is correct
4	Correct	12 ms	9968 KB	Output is correct
5	Correct	12 ms	9972 KB	Output is correct
6	Correct	13 ms	9980 KB	Output is correct
7	Correct	13 ms	9980 KB	Output is correct
8	Correct	13 ms	10020 KB	Output is correct
9	Correct	12 ms	10076 KB	Output is correct
10	Correct	12 ms	10076 KB	Output is correct
11	Correct	12 ms	10076 KB	Output is correct
12	Correct	12 ms	10076 KB	Output is correct
13	Correct	12 ms	10092 KB	Output is correct
14	Correct	12 ms	10092 KB	Output is correct
15	Correct	12 ms	10092 KB	Output is correct
16	Correct	12 ms	10092 KB	Output is correct
17	Correct	12 ms	10092 KB	Output is correct
18	Correct	12 ms	10092 KB	Output is correct
19	Correct	12 ms	10096 KB	Output is correct
20	Correct	12 ms	10096 KB	Output is correct
21	Correct	12 ms	10096 KB	Output is correct
22	Correct	12 ms	10096 KB	Output is correct
23	Correct	12 ms	10096 KB	Output is correct
24	Correct	12 ms	10096 KB	Output is correct
25	Correct	13 ms	10096 KB	Output is correct
26	Correct	12 ms	10096 KB	Output is correct
27	Correct	13 ms	10220 KB	Output is correct
28	Correct	12 ms	10220 KB	Output is correct
29	Correct	12 ms	10220 KB	Output is correct
30	Correct	12 ms	10220 KB	Output is correct
31	Correct	12 ms	10220 KB	Output is correct
32	Correct	12 ms	10220 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10220 KB	Output is correct
2	Correct	13 ms	10224 KB	Output is correct
3	Correct	14 ms	10308 KB	Output is correct
4	Correct	13 ms	10308 KB	Output is correct
5	Correct	14 ms	10308 KB	Output is correct
6	Correct	14 ms	10308 KB	Output is correct
7	Correct	13 ms	10308 KB	Output is correct
8	Correct	13 ms	10308 KB	Output is correct
9	Correct	14 ms	10308 KB	Output is correct
10	Correct	13 ms	10308 KB	Output is correct
11	Correct	13 ms	10308 KB	Output is correct
12	Correct	15 ms	10308 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	11884 KB	Output is correct
2	Correct	25 ms	11884 KB	Output is correct
3	Correct	33 ms	11884 KB	Output is correct
4	Correct	33 ms	11884 KB	Output is correct
5	Correct	24 ms	11884 KB	Output is correct
6	Correct	25 ms	11884 KB	Output is correct
7	Correct	26 ms	11884 KB	Output is correct
8	Correct	23 ms	11884 KB	Output is correct
9	Correct	21 ms	11884 KB	Output is correct
10	Correct	26 ms	11884 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	185 ms	28396 KB	Output is correct
2	Correct	183 ms	28396 KB	Output is correct
3	Correct	293 ms	28408 KB	Output is correct
4	Correct	291 ms	28408 KB	Output is correct
5	Correct	161 ms	28408 KB	Output is correct
6	Correct	156 ms	28408 KB	Output is correct
7	Correct	220 ms	28408 KB	Output is correct
8	Correct	127 ms	28408 KB	Output is correct
9	Correct	155 ms	28408 KB	Output is correct
10	Correct	193 ms	28408 KB	Output is correct

Subtask #5
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	591 ms	65300 KB	Output is correct
2	Correct	577 ms	65300 KB	Output is correct
3	Correct	952 ms	65300 KB	Output is correct
4	Correct	972 ms	65300 KB	Output is correct
5	Correct	521 ms	65300 KB	Output is correct
6	Correct	635 ms	65300 KB	Output is correct
7	Correct	710 ms	65300 KB	Output is correct
8	Correct	392 ms	65300 KB	Output is correct
9	Correct	401 ms	65300 KB	Output is correct
10	Correct	606 ms	65300 KB	Output is correct
11	Correct	586 ms	67616 KB	Output is correct
12	Correct	430 ms	67616 KB	Output is correct

답안 #42203

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 27.0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
27.0 / 27.0