Submission #44283

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44283	2018-03-31T08:53:27 Z	JustInCase	Lozinke (COCI17_lozinke)	C++17	90 / 100	545 ms	10412 KB

lozinke

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAX_N = 2e4 + 5;
const int MAX_S = 15;

//---------------------------------

struct Hash {
	static const int BASE = 131;
	static const int MOD = 1e9 + 7;
	static int basePowers[];

	int h[MAX_S];

	Hash(const string &s);
	void ComputeHash(const string &s);
	static void ComputeBasePowers();
	int CalculateModularInverse(int a, int mod);
	int GetSubstringHash(int low, int high);
};

int Hash::basePowers[MAX_S];

Hash::Hash(const string &s = "") {
	if(s.size() != 0) {
		ComputeHash(s);
	}
}

void Hash::ComputeHash(const string &s) {
	h[0] = 0;

	for(int i = 1; i <= s.size(); i++) {
		h[i] = (1ll * h[i - 1] + 1ll * (s[i - 1] - 'a' + 1) * basePowers[i]) % MOD;
	}
}

void Hash::ComputeBasePowers() {
	basePowers[0] = 1;

	for(int i = 1; i < MAX_S; i++) {
		basePowers[i] = (1ll * basePowers[i - 1] * BASE) % MOD;
	}
}

int Hash::CalculateModularInverse(int a, int mod) {
	if(mod == 0) {
		return 1;
	}
	
	if(mod % 2 == 0) {
		int p = CalculateModularInverse(a, mod / 2);
		return (1ll * p * p) % MOD;
	}
	else {
		return (1ll * CalculateModularInverse(a, mod - 1) * a) % MOD;
	}
}

int Hash::GetSubstringHash(int low, int high) {
	int substringHash = (1ll * (h[high] - h[low - 1]) * CalculateModularInverse(basePowers[low - 1], MOD - 2)) % MOD;
	if(substringHash < 0) {
		substringHash += MOD;
	}

	return substringHash;
}

//---------------------------------

string s[MAX_N];
Hash hs[MAX_N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	Hash::ComputeBasePowers();

	int n;
	cin >> n;
	
	unordered_map< int, int > cnt;
	for(int i = 0; i < n; i++) {
		cin >> s[i];

		hs[i] = Hash(s[i]);
		cnt[hs[i].h[s[i].size()]]++;
	}

	int ans = 0;
	for(int i = 0; i < n; i++) {
		unordered_map< int, bool > alreadyChecked;
		for(int low = 1; low <= s[i].size(); low++) {
			for(int high = low; high <= s[i].size(); high++) {
				int currSubstringHash = hs[i].GetSubstringHash(low, high);

				if(alreadyChecked.count(currSubstringHash) == 0) {
					ans += cnt[currSubstringHash]; 
					if(low == 1 && high == s[i].size()) {
						ans--;
					}
					
					alreadyChecked[currSubstringHash] = true;
				}
			}
		}
	}

	cout << ans << endl;
	return 0;
}

Compilation message

lozinke.cpp: In member function 'void Hash::ComputeHash(const string&)':
lozinke.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i <= s.size(); i++) {
                 ~~^~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:97:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int low = 1; low <= s[i].size(); low++) {
                    ~~~~^~~~~~~~~~~~~~
lozinke.cpp:98:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int high = low; high <= s[i].size(); high++) {
                        ~~~~~^~~~~~~~~~~~~~
lozinke.cpp:103:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(low == 1 && high == s[i].size()) {
                     ~~~~~^~~~~~~~~~~~~~

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1016 KB	Output is correct
2	Correct	2 ms	1096 KB	Output is correct
3	Correct	3 ms	1096 KB	Output is correct
4	Correct	4 ms	1156 KB	Output is correct
5	Correct	17 ms	1364 KB	Output is correct
6	Correct	29 ms	1408 KB	Output is correct
7	Correct	33 ms	1920 KB	Output is correct
8	Correct	47 ms	2176 KB	Output is correct
9	Correct	141 ms	2792 KB	Output is correct
10	Correct	267 ms	5460 KB	Output is correct
11	Correct	215 ms	5460 KB	Output is correct
12	Incorrect	494 ms	10224 KB	Output isn't correct
13	Correct	458 ms	10224 KB	Output is correct
14	Incorrect	361 ms	10224 KB	Output isn't correct
15	Correct	545 ms	10412 KB	Output is correct
16	Correct	534 ms	10412 KB	Output is correct
17	Correct	508 ms	10412 KB	Output is correct
18	Correct	347 ms	10412 KB	Output is correct
19	Correct	380 ms	10412 KB	Output is correct
20	Correct	284 ms	10412 KB	Output is correct