oj.uz

Submission #813434

# Submission time Handle Problem Language Result Execution time Memory
813434 2023-08-07T17:54:11 Z Divane Palinilap (COI16_palinilap) C++14
37 / 100
 73 ms 26628 KB 
    /* In the name of GOD */
     
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define F first
    #define S second 
    #define mk make_pair
    typedef long long ll;
    typedef long double ld;
    #define int long long
    typedef pair <int, int> pii;
    const int N = 200012, M = 1000696969, B = 679;
    int a[N], b[N];
    int ps[N];
    int pe[N];
    int A[26];
    int hr[N];
    int hl[N];
    int p[N];
    int n;
    vector <int> st[N], e[N];
     
    int getL (int l, int r) {
    	l = n - 1 - l;
    	r = n - 1 - r;
    	return (((hl[r] - hl[l - 1] * p[r - l + 1]) % M) + M) % M;
    }
     
    int getR (int l, int r) {
    	return (((hr[r] - hr[l - 1] * p[r - l + 1]) % M) + M) % M;
    }
     
    int32_t main () {
    	p[0] = 1;
    	for (int i = 1; i < N; i++) {
    		p[i] = p[i - 1] * B;
    		p[i] %= M;
    	}
    	string s, t;
    	cin >> t;
    	s = "#3#4#";
    	for (char c : t) {
    		s += c;
    		s += '#';
    	}
    	s += "2#1#";
    	n = (int)s.size();
    	int H = 0;
    	for (int i = 0; i < n; i++) {
    		H *= B;
    		H += s[i];
    		H %= M;
    		hr[i] = H;
    	}
    	reverse(s.begin(), s.end());
    	H = 0;
    	for (int i = 0; i < n; i++) {
    		H *= B;
    		H += s[i];
    		H %= M;
    		hl[i] = H;
    	}
    	reverse(s.begin(), s.end());
    	int ans = 0;
    	for (int i = 5; i < n - 5; i++) {
    		int l = 1, r = min(i, n - i - 1);
    		while (r - l > 1) {
    			int mid = (l + r) >> 1;
    			if (getR (i, i + mid - 1) == getL(i, i - mid + 1))
    				l = mid;
    			else
    				r = mid;
    		}
    		st[i - l].push_back(i);
    		e[i + l].push_back(i);
    		ans += (l / 2);
    		a[i] = l / 2;
    		ps [i + l - 1]--;
    		ps [i]++;
    		ps [i - 1]++;
    		ps [i - l]--;
    		int ol = l + 1;
    		l = 0, r = min(n - (i + ol) - 1, i - ol);
    		while (r - l > 1) {
    			int mid = (l + r) >> 1;
    			if (getR (i + ol, i + ol + mid - 1) == getL(i - ol, i - ol - mid + 1))
    				l = mid;
    			else
    				r = mid;
    		}
    		b[i] = l;
    	}
    	for (int i = n - 1; i >= 0; i--)
    		ps[i] = ps[i + 1] + ps[i];
    	int pps = 0;
    	int mx = ans;
    	for (int i = 0; i < n; i++) {
    		if (i >= 5 && i < n - 5 && i % 2) {
    			int ANS = ans;
    			ANS -= pps;
    			ANS += a[i];
    			for (int wef : st[i]) {
    				char c = s[wef + (wef - i)];
    				A[c - 'a'] += b[wef] / 2 + 1;
    			}
    			for (int wef : e[i]) {
    				char c = s[wef - (i - wef)];;
    				A[c - 'a'] += b[wef] / 2 + 1;
    			}
    			int MX = 0;
    			for (int i = 0; i < 26; i++) {
    				MX = max(MX, A[i]);
    				A[i] = 0;
    			}
    			mx = max(mx, MX + ANS);
    		}
    		if (i % 2)
    			pps += ps[i];
    	}
    	cout << mx - 1 << '\n';
    }

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12040 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 8 ms 12036 KB Output is correct
4 Correct 7 ms 11732 KB Output is correct
5 Correct 8 ms 11952 KB Output is correct
6 Correct 9 ms 12040 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 26628 KB Output isn't correct
2 Halted 0 ms 0 KB -