oj.uz

Submission #933692

# Submission time Handle Problem Language Result Execution time Memory
933692 2024-02-26T05:40:26 Z guagua0407 Palindromes (APIO14_palindrome) C++17
100 / 100
 179 ms 38560 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int p=29;
const int mod=1e9+7;
const int mxn=3e5+5;
int powv[mxn];
int hashr[mxn],hashl[mxn];
map<int,int> mp[mxn];

void build(string str){
    int n=str.length();
    powv[0]=1;
    for(int i=1;i<=n;i++){
        powv[i]=1ll*powv[i-1]*p%mod;
    }
    for(int i=1;i<n;i++){
        hashr[i]=(1ll*hashr[i-1]*p%mod+(str[i]-'a'+1))%mod;
    }
    for(int i=n-1;i>=1;i--){
        hashl[i]=(1ll*hashl[i+1]*p%mod+(str[i]-'a'+1))%mod;
    }
}

int get1(int l,int r){
    int ans=(hashl[l]-1ll*hashl[r+1]*powv[r-l+1]%mod)%mod;
    if(ans<0) ans+=mod;
    return ans;
}

int get2(int l,int r){
    int ans=(hashr[r]-1ll*hashr[l-1]*powv[r-l+1]%mod)%mod;
    if(ans<0) ans+=mod;
    return ans;
}

bool same(int l1,int r1,int l2,int r2){
    int v1=get1(l1,r1);
    int v2=get2(l2,r2);
    return v1==v2;
}

int main() {_
    string str;
    cin>>str;
    int n=(int)str.length();
    str="#"+str;
    build(str);
    priority_queue<pair<int,pair<int,int>>> pq;
    for(int i=1;i<=n;i++){
        {
            int l=0,r=min(i-1,n-i);
            while(l<r){
                int mid=(l+r+1)/2;
                if(same(i-mid,i-1,i+1,i+mid)){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            int val=get2(i-l,i+l);
            mp[2*l+1][val]++;
            if(mp[2*l+1][val]==1) pq.push({2*l+1,{i-l,i+l}});
        }
        {
            int l=0,r=min(i-1,n-i+1);
            while(l<r){
                int mid=(l+r+1)/2;
                if(same(i-mid,i-1,i,i+mid-1)){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            if(l>0){
                int val=get2(i-l,i+l-1);
                mp[2*l][val]++;
                if(mp[2*l][val]==1) pq.push({2*l,{i-l,i+l-1}});
            }
        }
    }
    ll ans=1;
    while(!pq.empty()){
        auto tmp=pq.top();
        pq.pop();
        int len=tmp.f;
        int l=tmp.s.f;
        int r=tmp.s.s;
        int val=get2(l,r);
        int cnt=mp[len][val];
        ans=max(ans,1ll*cnt*len);
        l++;
        r--;
        if(l<=r){
            int val2=get2(l,r);
            mp[r-l+1][val2]+=cnt;
            if(mp[r-l+1][val2]==cnt) pq.push({r-l+1,{l,r}});
        }
    }
    cout<<ans<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message

palindrome.cpp: In function 'void setIO(std::string)':
palindrome.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 4 ms 17000 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 4 ms 16988 KB Output is correct
21 Correct 4 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 4 ms 16988 KB Output is correct
24 Correct 4 ms 16988 KB Output is correct
25 Correct 4 ms 16988 KB Output is correct
26 Correct 4 ms 16988 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 4 ms 16984 KB Output is correct
29 Correct 4 ms 16988 KB Output is correct
30 Correct 4 ms 16988 KB Output is correct
31 Correct 5 ms 17048 KB Output is correct
32 Correct 4 ms 16988 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 17008 KB Output is correct
3 Correct 4 ms 17092 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 4 ms 16984 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 5 ms 17052 KB Output is correct
11 Correct 4 ms 17240 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17496 KB Output is correct
2 Correct 7 ms 17496 KB Output is correct
3 Correct 8 ms 17500 KB Output is correct
4 Correct 9 ms 17500 KB Output is correct
5 Correct 8 ms 17500 KB Output is correct
6 Correct 8 ms 17496 KB Output is correct
7 Correct 9 ms 17496 KB Output is correct
8 Correct 6 ms 16988 KB Output is correct
9 Correct 6 ms 16984 KB Output is correct
10 Correct 7 ms 17240 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 23136 KB Output is correct
2 Correct 54 ms 22784 KB Output is correct
3 Correct 49 ms 23044 KB Output is correct
4 Correct 60 ms 23044 KB Output is correct
5 Correct 39 ms 21840 KB Output is correct
6 Correct 44 ms 20872 KB Output is correct
7 Correct 55 ms 22064 KB Output is correct
8 Correct 33 ms 17496 KB Output is correct
9 Correct 35 ms 18580 KB Output is correct
10 Correct 41 ms 21580 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 34216 KB Output is correct
2 Correct 173 ms 35096 KB Output is correct
3 Correct 146 ms 38312 KB Output is correct
4 Correct 178 ms 38560 KB Output is correct
5 Correct 118 ms 32476 KB Output is correct
6 Correct 165 ms 33440 KB Output is correct
7 Correct 179 ms 32452 KB Output is correct
8 Correct 93 ms 18876 KB Output is correct
9 Correct 95 ms 18872 KB Output is correct
10 Correct 112 ms 29968 KB Output is correct
11 Correct 144 ms 33204 KB Output is correct
12 Correct 98 ms 20220 KB Output is correct