Submission #165184

#	Time	Username	Problem	Language	Result	Execution time	Memory
165184		theStaticMind	Lozinke (COCI17_lozinke)	C++14	90 / 100	441 ms	19320 KiB

lozinke

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
 //     freopen("q.gir","r",stdin);
 //     freopen("q.cik","w",stdout);
      int n;
      cin>>n;
      vector<string>arr(n);
      vector<int>H[n],h[n],Hh[n];
      map<int,int>data;
      for(int i=0;i<n;i++){
            string s;
            set<int> S;
            cin>>s;
            arr[i]=s;
            H[i].resize(s.length()+1,0);
            Hh[i]=h[i]=H[i];
            for(int j=1;j<=s.length();j++){
                  H[i][j]=(H[i][j-1]*29+s[j-1]-'a'+1)%modulo;
                  h[i][j]=(h[i][j-1]*31+s[j-1]-'a'+1)%mod;
                  Hh[i][j]=(Hh[i][j-1]*53+s[j-1]-'a'+1)%(modulo+2);
            }
            int K=29,T=31,X=53;
            for(int j=1;j<=s.length();j++){
                  K=29,T=31,X=53;
                  for(int k=j-1;k>=0;k--){
                        S.insert((H[i][j]-H[i][k]*K%modulo+modulo)%modulo+(h[i][j]-h[i][k]*T%mod+mod)%mod+(Hh[i][j]-Hh[i][k]*X%(modulo+2)+(modulo+2))%(modulo+2));
                        K=K*29%modulo;
                        T=T*31%mod;
                        X=X*53%(modulo+2);
                  }
            }
            for(set<int>::iterator itr=S.begin();itr!=S.end();itr++){
                  data[*itr]++;
            }
      }
      int ans=0;
      for(int i=0;i<n;i++){
            ans+=data[H[i].back()+h[i].back()+Hh[i].back()]-1;
      }
      cout<<ans;
}

Compilation message (stderr)

lozinke.cpp: In function 'int32_t main()':
lozinke.cpp:29:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=1;j<=s.length();j++){
                         ~^~~~~~~~~~~~
lozinke.cpp:35:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=1;j<=s.length();j++){
                         ~^~~~~~~~~~~~

• Subtask 1: 90 / 100