oj.uz

Submission #165733

# Submission time Handle Problem Language Result Execution time Memory
165733 2019-11-28T12:13:58 Z Sensei Lozinke (COCI17_lozinke) C++17
40 / 100
 1000 ms 32120 KB 
#include <bits/stdc++.h>

using namespace std;

const long long P = 53;
const long long MOD = 1e9 + 7;

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;
}

string st[MAXN + 7];
long long fullhash[MAXN + 7];
unordered_set<long long> subhashes[MAXN + 7];

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

	for (int i = 1; i <= N; i++) {
		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].insert(hash);
				if (ss == 0 && j + 1 == st[i].size()) {
					fullhash[i] = hash;
				}
			}
		}
	}

	long long ans = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i != j && subhashes[i].find(fullhash[j]) != subhashes[i].end()) {
				ans++;
			}
		}
	}

	cout << ans << "\n";

	return 0;
}

Compilation message

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

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 4 ms 2040 KB Output is correct
3 Correct 4 ms 2168 KB Output is correct
4 Correct 12 ms 2168 KB Output is correct
5 Correct 89 ms 2936 KB Output is correct
6 Correct 80 ms 3732 KB Output is correct
7 Correct 156 ms 3960 KB Output is correct
8 Correct 149 ms 4860 KB Output is correct
9 Execution timed out 1070 ms 10588 KB Time limit exceeded
10 Execution timed out 1074 ms 15992 KB Time limit exceeded
11 Execution timed out 1077 ms 15224 KB Time limit exceeded
12 Execution timed out 1085 ms 28152 KB Time limit exceeded
13 Execution timed out 1067 ms 28564 KB Time limit exceeded
14 Execution timed out 1077 ms 20600 KB Time limit exceeded
15 Execution timed out 1078 ms 30328 KB Time limit exceeded
16 Execution timed out 1087 ms 32120 KB Time limit exceeded
17 Execution timed out 1089 ms 11216 KB Time limit exceeded
18 Execution timed out 1075 ms 9720 KB Time limit exceeded
19 Execution timed out 1088 ms 24312 KB Time limit exceeded
20 Execution timed out 1084 ms 18552 KB Time limit exceeded