Submission #229540

#	Time	Username	Problem	Language	Result	Execution time	Memory
229540		Uzumaki_Naturoo	Rima (COCI17_rima)	C++14	0 / 140	138 ms	262148 KiB

rima

/// You just can't beat the person who never gives up
/// ICPC next year

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 5e5+5 ;

int n ;
string str ;

const int base = 29 ;
int mod[2] = {(int)1e9+9 ,(int)1e9+7};
int pwr(int b,int md){
    int p = md - 2 ;
    int res = 1 ;
    while(p){
        if(p&1) res = (1ll * res * b) %md;
        b = (1ll * b * b) %md;
        p >>= 1;
    }
    return res ;
}
int inv[2] = {pwr(base,mod[0]) ,pwr(base,mod[1])} ;
pair<int,int> push_back(pair<int,int> cur,int x){
    int val[2] = {cur.first,cur.second};
    for(int i=0;i<2;++i){
        val[i] = (1ll * val[i] * base) %mod[i];
        val[i] = (val[i] + x) %mod[i];
    }
    return make_pair(val[0],val[1]) ;
}
pair<int,int> pop_back(pair<int,int> cur,int v){
    int val[2] = {cur.first,cur.second};
    for(int i=0;i<2;++i){
        val[i] = ((val[i] - v) %mod[i] + mod[i]) %mod[i] ;
        val[i] = (1ll * val[i] * inv[i]) %mod[i];
    }
    return make_pair(val[0],val[1]) ;
}
pair<int,int> hash_val[N] ;
stack<int> lst[N] ;
int main(){
    cin >> n ;
    map<pair<int,int>,int> cnt ,cnt2 ;
    for(int i=0;i<n;++i){
        cin >> str ;
        reverse(str.begin(),str.end());
        pair<int,int> cur = {0,0} ;
        for(int j=0;j<str.size();++j){
            cur = push_back(cur,str[j]-'a'+1);
            lst[i].push(str[j]-'a'+1) ;
        }
        hash_val[i] = cur ;
        ++cnt[cur] ;
        ++cnt2[pop_back(cur,lst[i].top())];
    }
    int ans = 0 ;
    for(int i=0;i<n;++i){
        int cur = 0 ;
        pair<int,int> h = hash_val[i] ;
        while(lst[i].size()){
            if(!cnt.count(h)) break ;
            h = pop_back(h,lst[i].top());
            lst[i].pop();
            cur += cnt2[h] ;
        }
        ans = max(ans ,cur);
    }
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

rima.cpp: In function 'int main()':
rima.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<str.size();++j){
                     ~^~~~~~~~~~~

• Subtask 1: 0 / 140