oj.uz

Submission #625390

# Submission time Handle Problem Language Result Execution time Memory
625390 2022-08-10T10:09:54 Z NintsiChkhaidze Palinilap (COI16_palinilap) C++14
54 / 100
 1000 ms 28000 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define s second
#define f first
using namespace std;

const int N = 100005;
int mod = 1000000007,PR = 31,n,h[N],p[N],add[N][30],dlt[N],Rp[N],Rh[N];
string s;

bool check(int l1,int r1,int l2,int r2){
    long long val1 = h[r1];
    if (l1) val1 -= h[l1 - 1];
    val1%=mod;
    val1 = (val1+mod)%mod;
    
    long long val2 = Rh[l2];
    if (r2 < n - 1) val2 -= Rh[r2 + 1];
    val2 %= mod;
    val2 = (val2+mod)%mod;
    
    return ((val1 * Rp[r2])%mod == (val2 * p[l1])%mod);
}

int get(int L,int R){
    int res=0,l = 0,r = n;
    while (l <= r){
        int mid = (l + r)>>1;
        if (L - mid + 1 >= 0 && R + mid - 1 < n && check(L - mid + 1,L,R,R + mid - 1)) 
            res = mid, l = mid + 1;
        else 
            r = mid - 1;
    }
    return res;
}
signed main (){
    cin>>s;
    n = s.size();
    for (int i = 0; i < n; i++){
        if (i == 0){
            p[i] = 1;
            h[i] = (s[i] - 'a' + 1)%mod;
        }else{
            p[i] = (p[i - 1] * PR)%mod;
            h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1))%mod)%mod;
        }
    }
    
    for (int i = n - 1; i >= 0; i--){
        if (i == n - 1){
            Rp[i] = 1;
            Rh[i] = (s[i] - 'a' + 1)%mod;
        }else{
            Rp[i] = (Rp[i + 1] * PR)%mod;
            Rh[i] = (Rh[i + 1] + (Rp[i] * (s[i] - 'a' + 1))%mod)%mod;
        }
    }
    
    int base_ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = i; j <= min(n - 1,i + 1); j++){
            int len = get(i,j);
            base_ans += len;
            int l = i - len + 1,r = j + len - 1;
            
            if (i != j){
                int k = 0;
                for (int z = i - len + 1; z <= i; z++){
                    k--;
                    dlt[z] += k;
                }
                for (int z = j; z <= j + len - 1; z++){
                    dlt[z] += k;
                    k++;
                }
            }else{
                int k = 0;
                for (int z = i - len + 1; z <= i - 1; z++){
                    k--;
                    dlt[z] += k;
                }
                
                for (int z = i + 1; z <= j + len - 1; z++){
                    dlt[z] += k;
                    k++;
                }
            }
            
            if (l > 0 && r < n - 1){
                l--,r++;
                int val = get(l - 1,r + 1) + 1;
                add[l][s[r] - 'a' + 1] += val;
                add[r][s[l] - 'a' + 1] += val;
                // if (l == 1 && r == 3)
                //     cout<<val<<" "<<l<<" ^ "<<s[r]<<" & "<<r<<" ^ "<<s[l]<<endl;
            }
        }
    }
    
    int best_add=0,sum = 0;
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= 26; j++){
            if (j == s[i] - 'a' + 1) continue;
            // if (i==1 && j == 3){
            //     cout<<i<<" * "<<char(j + 'a' - 1)<<" "<<base_ans <<" add=" <<add[i][j] <<" del = "<<dlt[i]<<endl;
            // }
            
            if (add[i][j] + dlt[i] > best_add){
                // cout<<i<<" "<<char(j + 'a' - 1)<<" "<<base_ans + add[i][j] + dlt[i]<<endl;
                best_add = add[i][j] + dlt[i];   
            }
        }
    }
    cout<<best_add + base_ans;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:101:20: warning: unused variable 'sum' [-Wunused-variable]
  101 |     int best_add=0,sum = 0;
      |                    ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1732 KB Output is correct
2 Correct 18 ms 1728 KB Output is correct
3 Correct 11 ms 1620 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 8 ms 1432 KB Output is correct
6 Correct 10 ms 1700 KB Output is correct
7 Correct 9 ms 1684 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 28000 KB Output is correct
2 Execution timed out 1093 ms 19328 KB Time limit exceeded
3 Halted 0 ms 0 KB -