Submission #403244

#TimeUsernameProblemLanguageResultExecution timeMemory
403244penguinhackerLozinke (COCI17_lozinke)C++14
100 / 100
131 ms2652 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ar array const unsigned long long SEED = chrono::steady_clock::now().time_since_epoch().count(); mt19937 rng(SEED); const int M=1e9+7, B1=31, B2=53; int n; ll ans; map<string, int> oc[11]; map<ar<int, 2>, int> mp; void add(ar<int, 2>& a, char c) { a[0]=((ll)B1*a[0]+c)%M; a[1]=((ll)B2*a[1]+c)%M; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i=0; i<n; ++i) { string s; cin >> s; ++oc[s.size()][s]; } for (int i=1; i<=10; ++i) { for (auto& x : oc[i]) { set<ar<int, 2>> st; string s=x.first; ll cnt=x.second; ans+=(ll)cnt*(cnt-1); for (int i=0; i<s.size(); ++i) { ar<int, 2> hsh={}; for (int j=i; j<s.size(); ++j) { add(hsh, s[j]); st.insert(hsh); } } for (const ar<int, 2>& j : st) if (mp.count(j)) ans+=cnt*mp[j]; ar<int, 2> hsh={}; for (char c : s) add(hsh, c); mp[hsh]+=cnt; } } cout << ans; return 0; }

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for (int i=0; i<s.size(); ++i) {
      |                  ~^~~~~~~~~
lozinke.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int j=i; j<s.size(); ++j) {
      |                   ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...