Submission #1011935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011935		0npata	Lozinke (COCI17_lozinke)	C++17	70 / 100	186 ms	13604 KiB

lozinke

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define vec vector

const int MX = 1e9+7;

mt19937 rng(54);

int rng_next(int mx) {
	return uniform_int_distribution<int32_t>(0, mx)(rng);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vec<string> a(n);

	for(int i = 0; i<n; i++) cin >> a[i];

	vec<int> pos_hash(10);
	vec<int> let_hash(26);

	for(int i = 0; i<10; i++) {
		pos_hash[i] = rng_next(MX);
	}
	for(int i = 0; i<26; i++) {
		let_hash[i] = rng_next(MX);
	}

	map<int, int> cnt;

	for(int i = 0; i<a.size(); i++) {
		set<int> subs;
		for(int j = 0; j < a[i].size(); j++) {
			int hash = 0;
			for(int k = j; k<a[i].size(); k++) {
				int pos = k-j;
				hash += pos_hash[pos] * let_hash[a[i][k]-'a'];
				hash %= MX;
				subs.insert(hash);
			}
		}

		for(int subh : subs) {
			cnt[subh] += 1;
		}
	}

	int ans = 0;
	for(int i = 0; i<n; i++) {
		int hash = 0;
		for(int j = 0; j<a[i].size(); j++) {
			hash += pos_hash[j] * let_hash[a[i][j]-'a'];
			hash %= MX;
		}
		ans += cnt[hash]-1;
	}

	cout << ans << '\n';

}

Compilation message (stderr)

lozinke.cpp: In function 'int32_t main()':
lozinke.cpp:37:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0; i<a.size(); i++) {
      |                 ~^~~~~~~~~
lozinke.cpp:39:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j = 0; j < a[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~
lozinke.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int k = j; k<a[i].size(); k++) {
      |                   ~^~~~~~~~~~~~
lozinke.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j = 0; j<a[i].size(); j++) {
      |                  ~^~~~~~~~~~~~

• Subtask 1: 70 / 100