oj.uz

답안 #44282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44282 2018-03-31T08:52:39 Z JustInCase Lozinke (COCI17_lozinke) C++17
90 / 100
 526 ms 11580 KB 
#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

# 결과 실행 시간 메모리 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