oj.uz

답안 #1008968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008968 2024-06-27T07:12:03 Z BF001 Palinilap (COI16_palinilap) C++17
0 / 100
 34 ms 18776 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 100005

int n, md = 1e9 + 7, base = 32, pre[N], f[30][N];
vector<int> pw;
string s, rs;

struct hsh
{
	vector<int> gt;
	hsh(string s){
		int len = (int) s.size();
		while ((int) pw.size() - 1 < len){
			pw.push_back(pw.back() * base % md);
		}
		gt.resize(len + 1, 0);
		for (int i = 1; i <= len; i++){
			gt[i] = (gt[i - 1] * base + s[i - 1] - 'a' + 1) % md;
		}
	}
	int gethsh(int l, int r){
		return (gt[r] - gt[l - 1] * pw[r - l + 1] + md * md) % md;
	}	
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> s;
    rs = s;
    reverse(rs.begin(), rs.end());

    pw.push_back(1);
    hsh h1 = hsh(s);
    hsh h2 = hsh(rs);

    int n = (int) s.size();
    s = " " + s;
    rs = " " + rs;
    int sum = 0;

    for (int i = 1; i <= n; i++){
    	for (int j = i; j <= min(n, i + 1); j++){
    		int l = 1, r = min(i, n - j + 1), rt = 1;
    		if (s[i] == s[j]){
	    		while (l <= r){
	    			int mid = (l + r) >> 1;
	    			int ps = j, ps2 = j + mid - 1;
	    			if (h1.gethsh(i - mid + 1, i) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
	    				rt = mid;
	    				l = mid + 1;
	    			}
	    			else r = mid - 1;
	    		} 
	    		sum += rt;
	    		l = i - rt + 1, r = j + rt - 1;
	    		if (i != j){
	   				pre[l] += 1;
	    			pre[r + 1] += -1;
	    		}
	    		else {
	    			pre[l] ++;
	    			pre[i]--;
	    			pre[i + 1]++;
	    			pre[r + 1]--;
	    		}
	    	}
    		int ii = l - 1, jj = r + 1;
    		if (s[i] != s[j]) ii = i, jj = j;
    		if (ii < 1 || jj > n) continue;
    		l = 2, r = min(ii, n - jj + 1), rt = 1;
    		while (l <= r){
    			int mid = (l + r) >> 1;
    			int ps = jj  + 1, ps2 = jj + mid - 1;
    			if (h1.gethsh(ii - mid + 1, ii - 1) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
    				rt = mid;
    				l = mid + 1;
    			}
    			else r = mid - 1;
    		}
    		f[s[ii] - 'a' + 1][jj] += rt;
    		f[s[jj] - 'a' + 1][ii] += rt;
    	}
    }

    int res = sum;

    for (int i = 1; i <= n; i++){
    	pre[i] += pre[i - 1];
    	for (int j = 1; j <= 26; j++){
    		res = max(res , sum - pre[i] + f[j][i]);
    	}
    }

    cout << res;

    return 0;
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 18776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Incorrect 2 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 8140 KB Output isn't correct
2 Halted 0 ms 0 KB -