Submission #229540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
229540	2020-05-04T23:57:17 Z	Uzumaki_Naturoo	Rima (COCI17_rima)	C++14	0 / 140	138 ms	262148 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	130 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Runtime error	128 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	127 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Runtime error	136 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	134 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	132 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	132 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	138 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	126 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	133 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)