oj.uz

Submission #165738

# Submission time Handle Problem Language Result Execution time Memory
165738 2019-11-28T12:24:20 Z Sensei Lozinke (COCI17_lozinke) C++17
85 / 100
 1000 ms 34936 KB 
#include <bits/stdc++.h>

using namespace std;

const long long P = 61;
const long long MOD = 1e16 + 3;

const int MAXN = 2e4;

long long add (long long x, long long y) {
	return ((x % MOD) + (y % MOD)) % MOD;
}

long long mul (long long x, long long y) {
	return ((x % MOD) * (y % MOD)) % MOD;
}

// vector<char> st[MAXN + 7];
string st[MAXN + 7];
long long fullhash[MAXN + 7];
// vector<long long> subhashes[MAXN + 7];
set<long long> subhashes[MAXN + 7];
char buff[12];
multiset<long long> fullhashes;

int main () {
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		// scanf("%s", buff);

		// for (int j = 0; buff[j] != 0; j++) {
		// 	st[i].push_back(buff[j]);
		// }

		cin >> st[i];
	}

	for (int i = 1; i <= N; i++) {
		for (int ss = 0; ss < st[i].size(); ss++) {
			long long hash = 0;

			for (int j = ss; j < st[i].size(); j++) {
				hash = mul(hash, P);
				hash = add(hash, st[i][j] - 'a' + 1);

				// subhashes[i].push_back(hash);
				subhashes[i].insert(hash);
				if (ss == 0 && j + 1 == st[i].size()) {
					fullhash[i] = hash;
					fullhashes.insert(hash);
				}
			}
		}

		// sort(subhashes[i].begin(), subhashes[i].end());
	}

	long long ans = 0;

	for (int i = 1; i <= N; i++) {
		for (long long hash : subhashes[i]) {
			ans += fullhashes.count(hash);
		}

		ans--;
	}

	cout << ans << "\n";

	return 0;
}

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int ss = 0; ss < st[i].size(); ss++) {
                    ~~~^~~~~~~~~~~~~~
lozinke.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = ss; j < st[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~
lozinke.cpp:50:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ss == 0 && j + 1 == st[i].size()) {
                    ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 1912 KB Output is correct
3 Correct 4 ms 2040 KB Output is correct
4 Correct 5 ms 2012 KB Output is correct
5 Correct 10 ms 2808 KB Output is correct
6 Correct 14 ms 3584 KB Output is correct
7 Correct 20 ms 3844 KB Output is correct
8 Correct 18 ms 4984 KB Output is correct
9 Correct 307 ms 11356 KB Output is correct
10 Correct 108 ms 17272 KB Output is correct
11 Correct 650 ms 16376 KB Output is correct
12 Correct 186 ms 30820 KB Output is correct
13 Correct 218 ms 30456 KB Output is correct
14 Correct 453 ms 22748 KB Output is correct
15 Correct 244 ms 33260 KB Output is correct
16 Correct 221 ms 34936 KB Output is correct
17 Execution timed out 1077 ms 12408 KB Time limit exceeded
18 Execution timed out 1083 ms 10488 KB Time limit exceeded
19 Correct 228 ms 26452 KB Output is correct
20 Execution timed out 1084 ms 20216 KB Time limit exceeded