oj.uz

Submission #116805

# Submission time Handle Problem Language Result Execution time Memory
116805 2019-06-14T01:19:05 Z HungAnhGoldIBO2020 Lozinke (COCI17_lozinke) C++11
10 / 100
 760 ms 4088 KB 
#include<iostream>
#include<set>
#define hash hash1
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];
int 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

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

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1024 KB Output isn't correct
2 Correct 2 ms 896 KB Output is correct
3 Incorrect 3 ms 1024 KB Output isn't correct
4 Correct 4 ms 1024 KB Output is correct
5 Incorrect 6 ms 1152 KB Output isn't correct
6 Incorrect 8 ms 1152 KB Output isn't correct
7 Incorrect 11 ms 1280 KB Output isn't correct
8 Incorrect 9 ms 1280 KB Output isn't correct
9 Incorrect 168 ms 2476 KB Output isn't correct
10 Incorrect 41 ms 2432 KB Output isn't correct
11 Incorrect 347 ms 3200 KB Output isn't correct
12 Incorrect 62 ms 3200 KB Output isn't correct
13 Incorrect 75 ms 3936 KB Output isn't correct
14 Incorrect 227 ms 3976 KB Output isn't correct
15 Incorrect 92 ms 4088 KB Output isn't correct
16 Incorrect 76 ms 3968 KB Output isn't correct
17 Incorrect 41 ms 3964 KB Output isn't correct
18 Incorrect 35 ms 3968 KB Output isn't correct
19 Incorrect 135 ms 3960 KB Output isn't correct
20 Incorrect 760 ms 3968 KB Output isn't correct