/// 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 p[N][2] = {{1, 1}} ;
int inv[N][2] = {{1, 1}} ;
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 ;
}
void init(){
for(int i=1;i<N;++i)
for(int j=0;j<2;++j){
p[i][j] = (1ll * p[i-1][j] * base) %mod[j] ;
inv[i][j] = pwr(p[i][j], mod[j]) ;
}
}
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 val[2] = {cur.first,cur.second};
for(int i=0;i<2;++i){
int v = val[i] %base ;
val[i] = ((val[i] - v) %mod[i] + mod[i]) %mod[i] ;
val[i] = (1ll * val[i] * inv[1][i]) %mod[i];
}
return make_pair(val[0],val[1]) ;
}
pair<int,int> hash_val[N] ;
int main(){
init() ;
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 i=0;i<str.size();++i){
cur = push_back(cur,str[i]-'a'+1);
}
hash_val[i] = cur ;
++cnt[cur] ;
++cnt2[pop_back(cur)];
}
int ans = 0 ;
for(int i=0;i<n;++i){
int cur = 0 ;
pair<int,int> h = hash_val[i] ;
while(h!=make_pair(0,0)){
if(!cnt.count(h)) break ;
h = pop_back(h);
cur += cnt2[h] ;
}
ans = max(ans ,cur);
}
printf("%d",ans);
return 0;
}
Compilation message
rima.cpp: In function 'int main()':
rima.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<str.size();++i){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
489 ms |
8312 KB |
Output isn't correct |
| 2 |
Incorrect |
490 ms |
8184 KB |
Output isn't correct |
| 3 |
Incorrect |
491 ms |
8312 KB |
Output isn't correct |
| 4 |
Execution timed out |
1097 ms |
48632 KB |
Time limit exceeded |
| 5 |
Incorrect |
695 ms |
11416 KB |
Output isn't correct |
| 6 |
Incorrect |
538 ms |
9488 KB |
Output isn't correct |
| 7 |
Incorrect |
532 ms |
9224 KB |
Output isn't correct |
| 8 |
Incorrect |
524 ms |
9204 KB |
Output isn't correct |
| 9 |
Incorrect |
723 ms |
13080 KB |
Output isn't correct |
| 10 |
Incorrect |
527 ms |
9356 KB |
Output isn't correct |
