Submission #116839

#	Time	Username	Problem	Language	Result	Execution time	Memory
116839		ntrung03	Lozinke (COCI17_lozinke)	C++17	60 / 100	378 ms	14716 KiB

lozinke

#pragma GCC optimize("Ofast")
#include <stdio.h>
#include <string.h>
#include <set>
#include <utility>
#include <map>
using namespace std;
#define int long long
#define mod 1204755107
#define base 31
char s[20002][12];
int h[20002][12];
int p[12];
signed main() {
	int n;
	scanf("%lld\n",&n);
	p[0] = 1;
	for(int i=1;i<12;i++)p[i] = (p[i-1]*base)%mod;
	int res = 0;
	for(int i=0;i<n;i++) scanf("%s\n",s[i]);
	map<pair<int,int>,int> hashes;
	for(int i=0;i<n;i++)
	{
		int l = strlen(s[i]);
		for(int j=0;j<l;j++)
		{
			h[i][j] = (j>0?h[i][j-1]:0);
			h[i][j] = ((h[i][j]*base)%mod+s[i][j]-'a'+1)%mod;
		}
		hashes[{h[i][l-1],l}]+=1;
	}
	for(int k =0;k<n;k++)
	{
		int l = strlen(s[k]);
		set<pair<int,int>> ck;
		for(int i=0;i<l;i++)
		for(int j=i;j<l;j++){
			long long ph = h[k][j]-(i>0?h[k][i-1]*p[j-i+1]:0)%mod;
			pair<int,int> hh = {ph,j-i+1};
			if(ck.count(hh)) continue;
			res+=hashes[hh];
			ck.insert(hh);
			if(i==0&&j==l-1) res-=1;
		}
	}
	printf("%lld",res);
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld\n",&n);
  ~~~~~^~~~~~~~~~~~~
lozinke.cpp:20:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%s\n",s[i]);
                       ~~~~~^~~~~~~~~~~~~

• Subtask 1: 60 / 100