Submission #632901

#TimeUsernameProblemLanguageResultExecution timeMemory
632901racsosabeSavez (COCI15_savez)C++14
0 / 120
108 ms31652 KiB
#include<bits/stdc++.h> using namespace::std; const int B[] = {311, 257}; const int MOD = 1e9 + 7; const int N = 2000000 + 5; int mul(int a, int b){ return (1ll * a * b) % MOD; } int pow_mod(int a, int b){ int r = 1; while(b){ if(b & 1) r = mul(r, a); a = mul(a, a); b >>= 1; } return r; } int n; char s[N]; int pot[2][N]; int poti[2][N]; int prefix[2][N]; map<pair<int, int>, int> best; void init(){ for(int id = 0; id < 2; id++){ pot[id][0] = 1; for(int i = 1; i < N; i++) pot[id][i] = mul(pot[id][i - 1], B[id]); poti[id][N - 1] = pow_mod(pot[id][N - 1], MOD - 2); for(int i = N - 2; i >= 0; i--) poti[id][i] = mul(poti[id][i + 1], B[id]); } } bool check(int l, int len){ for(int id = 0; id < 2; id++){ int L = prefix[id][l]; int R = mul((prefix[id][len] + MOD - prefix[id][len - l]), poti[id][len - l]); if(L != R) return false; } return true; } int main(){ init(); scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%s", s + 1); int len = strlen(s + 1); for(int id = 0; id < 2; id++) for(int j = 1; j <= len; j++) prefix[id][j] = (prefix[id][j - 1] + mul(pot[id][j], s[j])) % MOD; for(int l = 1; l <= len; l++){ if(check(l, len)){ int cur = 1 + (best.count(make_pair(prefix[0][l], prefix[1][l])) ? best[make_pair(prefix[0][l], prefix[1][l])] : 0); best[make_pair(prefix[0][len], prefix[1][len])] = cur; } } } int ans = 0; for(auto e : best){ if(ans < e.second) ans = e.second; } printf("%d\n", ans); return 0; }

Compilation message (stderr)

savez.cpp: In function 'int main()':
savez.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
savez.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%s", s + 1);
      |   ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...