Submission #116806

#	Time	Username	Problem	Language	Result	Execution time	Memory
116806		HungAnhGoldIBO2020	Lozinke (COCI17_lozinke)	C++11	10 / 100	752 ms	3932 KiB

lozinke

#include<iostream>
#include<set>
#define hash hash1
#define int long long
using namespace std;
const int N=2e4+2;
const int base=79;
const int mod=1e9+7;
string s[N];
long long hash1[N][12],mul[12];
multiset<int> lis[12],lis1[12];
signed main(){
	int n,i,j,k,l;
	long long ans=0,cac;
	cin>>n;
	string t;
	mul[0]=1;
	for(i=1;i<=10;i++){
		mul[i]=(mul[i-1]*base)%mod;
	}
	for(i=1;i<=n;i++){
		cin>>s[i];
		t=s[i];
		for(j=0;j<t.size();j++){
			hash1[i][j+1]=(hash[i][j]*base+(int)(t[j]-'a'+1));
		}
		lis[t.size()].insert(hash[i][t.size()]);
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=s[i].size();j++){
			for(k=j;k<=s[i].size();k++){
				if(j==1&&k==s[i].size()){
					ans--;
				}
				cac=((hash[i][k]-hash[i][j-1]*mul[k-j+1])%mod+mod)%mod;
				if(!lis1[k-j+1].count(cac)){
					lis1[k-j+1].insert(cac);
				}
				else{
					continue;
				}
				ans+=lis[k-j+1].count(cac);
			}
		}
		for(j=1;j<=10;j++){
			lis1[j].clear();
		}
	}
	cout<<ans;
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:24:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<t.size();j++){
           ~^~~~~~~~~
lozinke.cpp:30:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1;j<=s[i].size();j++){
           ~^~~~~~~~~~~~~
lozinke.cpp:31:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=j;k<=s[i].size();k++){
            ~^~~~~~~~~~~~~
lozinke.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j==1&&k==s[i].size()){
              ~^~~~~~~~~~~~~
lozinke.cpp:13:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l;
              ^

• Subtask 1: 10 / 100