oj.uz

Submission #116867

# Submission time Handle Problem Language Result Execution time Memory
116867 2019-06-14T03:03:15 Z HungAnhGoldIBO2020 Lozinke (COCI17_lozinke) C++11
10 / 100
 791 ms 5120 KB 
#include<iostream>
#include<set>
#include<string>
#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

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

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1024 KB Output isn't correct
2 Correct 3 ms 1024 KB Output is correct
3 Incorrect 3 ms 1024 KB Output isn't correct
4 Correct 3 ms 1024 KB Output is correct
5 Incorrect 6 ms 1152 KB Output isn't correct
6 Incorrect 6 ms 1280 KB Output isn't correct
7 Incorrect 11 ms 1408 KB Output isn't correct
8 Incorrect 8 ms 1408 KB Output isn't correct
9 Incorrect 198 ms 3064 KB Output isn't correct
10 Incorrect 35 ms 3200 KB Output isn't correct
11 Incorrect 355 ms 4088 KB Output isn't correct
12 Incorrect 50 ms 4096 KB Output isn't correct
13 Incorrect 56 ms 4992 KB Output isn't correct
14 Incorrect 232 ms 5120 KB Output isn't correct
15 Incorrect 71 ms 4992 KB Output isn't correct
16 Incorrect 63 ms 4992 KB Output isn't correct
17 Incorrect 29 ms 4992 KB Output isn't correct
18 Incorrect 26 ms 4992 KB Output isn't correct
19 Incorrect 95 ms 4992 KB Output isn't correct
20 Incorrect 791 ms 5120 KB Output isn't correct