Submission #44282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44282	2018-03-31T08:52:39 Z	JustInCase	Lozinke (COCI17_lozinke)	C++17	90 / 100	526 ms	11580 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	3 ms	888 KB	Output is correct
2	Correct	2 ms	1132 KB	Output is correct
3	Correct	4 ms	1228 KB	Output is correct
4	Correct	5 ms	1228 KB	Output is correct
5	Correct	17 ms	1472 KB	Output is correct
6	Correct	28 ms	1660 KB	Output is correct
7	Correct	31 ms	2088 KB	Output is correct
8	Correct	46 ms	2504 KB	Output is correct
9	Correct	138 ms	3056 KB	Output is correct
10	Correct	239 ms	5756 KB	Output is correct
11	Correct	220 ms	5756 KB	Output is correct
12	Incorrect	492 ms	10776 KB	Output isn't correct
13	Correct	427 ms	10776 KB	Output is correct
14	Incorrect	340 ms	10776 KB	Output isn't correct
15	Correct	524 ms	11580 KB	Output is correct
16	Correct	526 ms	11580 KB	Output is correct
17	Correct	503 ms	11580 KB	Output is correct
18	Correct	342 ms	11580 KB	Output is correct
19	Correct	380 ms	11580 KB	Output is correct
20	Correct	281 ms	11580 KB	Output is correct