Submission #116812

#	Time	Username	Problem	Language	Result	Execution time	Memory
116812		HungAnhGoldIBO2020	Lozinke (COCI17_lozinke)	C++11	10 / 100	780 ms	5164 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=998244353;
string s[N];
long long hash1[N][20],mul[20];
multiset<int> lis[20],lis1[20];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k;
	long long ans=0,cac;
	cin>>n;
	string t;
	mul[0]=1;
	for(i=1;i<=12;i++){
		mul[i]=(mul[i-1]*base)%mod;
	}
	for(i=1;i<=n;i++){
		cin>>s[i];
		t=s[i];
		hash1[i][0]=0;
		for(j=0;j<t.size();j++){
			hash1[i][j+1]=(hash1[i][j]*base+(int)(t[j]-'a'+1));
		}
		lis[t.size()].insert(hash1[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++){
				cac=((hash1[i][k]-hash1[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;
				}
				if(j==1&&k==s[i].size()){
					ans--;
				}
				ans+=lis[k-j+1].count(cac);
			}
		}
		for(j=1;j<=20;j++){
			lis1[j].clear();
		}
	}
	cout<<ans;
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:27:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<t.size();j++){
           ~^~~~~~~~~
lozinke.cpp:33:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1;j<=s[i].size();j++){
           ~^~~~~~~~~~~~~
lozinke.cpp:34:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=j;k<=s[i].size();k++){
            ~^~~~~~~~~~~~~
lozinke.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j==1&&k==s[i].size()){
              ~^~~~~~~~~~~~~

• Subtask 1: 10 / 100